Introduction

We consider a generalized symmetric definite eigenvalue problem of the form

$$(A - \lambda B)x=0$$

with real symmetric $n$ by $n$ matrices $A$ and $B$, assuming that $A$ is positive definite. That describes a regular matrix pencil $A - \lambda B$ with a discrete spectrum, a set of $n$ real, some possibly infinite, eigenvalues $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$. If $B$ is nonsingular, all eigenvalues are finite. If $B$ is positive semidefinite (e.g., $B=I$), all eigenvalues are positive, and we consider the problem of computing the smallest $m$ eigenvalues of the pencil $A - \lambda B$. When $B$ is indefinite, it is convenient to consider the pencil $B - \mu A$ with eigenvalues

$$\mu = \frac 1 \lambda, \quad \mu_{\min} = \mu_n \leq \cdots \leq \mu_1 = \mu_{\max},$$

where we want to compute the largest $m$ eigenvalues, $\mu_1, \ldots, \mu_m$. The problem of computing $m$ smallest eigenvalues $\mu_i$ can be reformulated as the previous one by replacing $B$ with $-B$. In buckling, both largest and smallest eigenvalues $\mu_i$ are of interest.

It is well known that (right) eigenvectors $x_i$, satisfying $(B - \mu_i A) x_i = 0$, can be chosen orthogonal in the following sense:

$$(x_i,A x_j) = (x_i, B x_j) = 0, \qquad i \neq j.$$

An important class of eigenproblems is the class of mesh eigenproblems, arising from discretizations of boundary value problems with self-adjoint differential operators of mathematical physics. The following properties are typical for mesh eigenproblems:

• The size $n$ of $A$ and $B$ is big, and is much larger than the number $m$ of required eigenpairs. Sometimes, a family of similar eigenproblems with increasing $n$ must be solved.
• $A$ and $B$ are sparse. Very large matrices cannot always fit in available memory even when using a sparse representation. In some situations, matrices $A$ and $B$ are not available in an explicit matrix form.
• No cheap factorization of $A$, or any matrix of the form $A + \beta B$, is available. The only operation we can perform with $A$ is multiplication of a vector by $A$.
• Cheap factorization of $B$ may sometimes be available, but, in general, the only operation we can do efficiently with $B$ is multiplication of a vector by $B$.
• The matrix $A$ is ill-conditioned. Usually, $B$ has a smaller condition number than $A$.
• The number of wanted eigenpairs $m$ can be chosen such that eigenvalues of interest are well separated from the rest of the spectrum; in other words, the ratio
  
  $$\frac{ \mu_m - \mu_{m+1} } { \mu_{\max} - \mu_{\min}}$$
  
  
  is not too small. This means that the invariant subspace of the matrix $A^{-1}B$ spanned by the eigenvectors of interest is well conditioned, thus the problem of computing $m$ eigenpairs is well posed. Such property can be established in many applications when the spectrum of the pencil $B - \mu A$ approximates a spectrum of a compact operator, such that zero is the only point of condensation of the approximate eigenvalues.

Such problems appear, e.g., in structural mechanics, where it is usual to call $A$ a stiffness matrix and $B$ a mass matrix. A mass matrix is usually positive definite, but in some applications, e.g., in buckling, the matrix $B$ is only nonnegative, or even indefinite, while $A$ is positive definite.

In the rest of the section, for brevity we deal with the pencil $B - \mu A$ only. With $B=I$ and $\lambda = 1 / \mu$, our results and arguments are readily applied for the pencil $A - \lambda I$.

Now, we briefly consider two traditional methods for such generalized eigenproblems.

One popular approach is based on multiplication by a shift-and-invert operator:

$$x^{(i+1)}=(B - \mu A)^{-1}Ax^{(i)};$$

see §4.3. It lets us quickly compute the eigenvalues closest to the shift $\mu$, assuming that this operation may be implemented with an explicit efficient triangular factorization of $B - \mu A$. With a properly chosen variable shift, e.g., based on the Rayleigh quotient (x) = (x,Bx)(x,Ax), the convergence is cubic for symmetric eigenproblems. However, for very large problems such factorizations are usually too expensive. Instead of explicit factorization, an approximate solution of the corresponding linear system is possible, e.g., using an iterative system solver. Then we obtain an inner-outer iterative method, where outer iterations may slow down significantly for an insufficient number of inner steps. If we take into account the total number of inner-outer iterative steps, the convergence is usually only linear.

If a preconditioned iterative solver is used for inner iterations, such a method becomes a preconditioned eigensolver. We shall discuss this method later, in §11.3.7.

Another approach can be used if $B$ is efficiently factorizable, so that we can multiply vectors by $AB^{-1},$ or $B^{-1}A,$ and use traditional methods like the Lanczos method; see §4.4. In this case, a single iteration is not too expensive, but the convergence may be slow. If $B$ is indefinite, then we need to find eigenvalues $\lambda_i$ in the middle of the spectrum using polynomial methods, which is known to be a hard problem. If $B$ is positive definite, then the situation is simpler, as we want to find the extreme (smallest) eigenvalues $\lambda_i$. Still, the ratio

$$\frac{\lambda_{m+1} - \lambda_m}{\lambda_{\max} - \lambda_{\min}}$$

that typically characterizes the speed of convergence for $\lambda_m$ is small because of the large denominator, which is a sign of possibly slow convergence.

Thus, the traditional approaches considered above are usually inefficient for very large eigenproblems. Preconditioning is a key for significant improvement of the performance.