M. E. Argentati

A. V. Knyazev, M. E. Argentati, I. Lashuk et al.

We describe our software package Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) publicly released recently. BLOPEX is available as a stand-alone serial library, as an external package to PETSc (``Portable, Extensible Toolkit for Scientific Computation'', a general purpose suite of tools for the scalable solution of partial differential equations and related problems developed by Argonne National Laboratory), and is also built into {\it hypre} (``High Performance Preconditioners'', scalable linear solvers package developed by Lawrence Livermore National Laboratory). The present BLOPEX release includes only one solver--the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) method for symmetric eigenvalue problems. {\it hypre} provides users with advanced high-quality parallel preconditioners for linear systems, in particular, with domain decomposition and multigrid preconditioners. With BLOPEX, the same preconditioners can now be efficiently used for symmetric eigenvalue problems. PETSc facilitates the integration of independently developed application modules with strict attention to component interoperability, and makes BLOPEX extremely easy to compile and use with preconditioners that are available via PETSc. We present the LOBPCG algorithm in BLOPEX for {\it hypre} and PETSc. We demonstrate numerically the scalability of BLOPEX by testing it on a number of distributed and shared memory parallel systems, including a Beowulf system, SUN Fire 880, an AMD dual-core Opteron workstation, and IBM BlueGene/L supercomputer, using PETSc domain decomposition and {\it hypre} multigrid preconditioning. We test BLOPEX on a model problem, the standard 7-point finite-difference approximation of the 3-D Laplacian, with the problem size in the range $10^5-10^8$.

M. E. Argentati, A. V. Knyazev, C. C. Paige et al.

The Rayleigh-Ritz method is widely used for eigenvalue approximation. Given a matrix $X$ with columns that form an orthonormal basis for a subspace $\X$, and a Hermitian matrix $A$, the eigenvalues of $X^HAX$ are called Ritz values of $A$ with respect to $\X$. If the subspace $\X$ is $A$-invariant then the Ritz values are some of the eigenvalues of $A$. If the $A$-invariant subspace $\X$ is perturbed to give rise to another subspace $\Y$, then the vector of absolute values of changes in Ritz values of $A$ represents the absolute eigenvalue approximation error using $\Y$. We bound the error in terms of principal angles between $\X$ and $\Y$. We capitalize on ideas from a recent paper [DOI: 10.1137/060649070] by A. Knyazev and M. Argentati, where the vector of absolute values of differences between Ritz values for subspaces $\X$ and $\Y$ was weakly (sub-)majorized by a constant times the sine of the vector of principal angles between $\X$ and $\Y$, the constant being the spread of the spectrum of $A$. In that result no assumption was made on either subspace being $A$-invariant. It was conjectured there that if one of the trial subspaces is $A$-invariant then an analogous weak majorization bound should only involve terms of the order of sine squared. Here we confirm this conjecture. Specifically we prove that the absolute eigenvalue error is weakly majorized by a constant times the sine squared of the vector of principal angles between the subspaces $\X$ and $\Y$, where the constant is proportional to the spread of the spectrum of $A$. For many practical cases we show that the proportionality factor is simply one, and that this bound is sharp. For the general case we can only prove the result with a slightly larger constant, which we believe is artificial.

A. V. Knyazev, M. E. Argentati

Many inequality relations between real vector quantities can be succinctly expressed as "weak (sub)majorization" relations. We explain these ideas and apply them in several areas: angles between subspaces, Ritz values, and graph Laplacian spectra, which we show are all surprisingly related... An application of our Ritz values weak majorization result for Laplacian graph spectra comparison is suggested, based on the possibility to interpret eigenvalues of the edge Laplacian of a given graph as Ritz values of the edge Laplacian of the complete graph. We prove that $ \sum_k |\lambda1_k - \lambda2_k| \leq n l,$ where $\lambda1_k$ and $\lambda2_k$ are all ordered elements of the Laplacian spectra of two graphs with the same $n$ vertices and with $l$ equal to the number of differing edges.