next up previous contents index
Next: Structure of the Spectral Up: The Implicitly Restarted Arnoldi Previous: Block Methods

The Generalized Eigenvalue Problem

A typical source of large scale eigenproblems is through a discrete form of a continuous problem. The resulting finite dimensional problems become large due to accuracy requirements and spatial dimensionality. Typically this takes the form

where ${\bf A}$ is a finite dimensional approximation to the continuous operator obtained either through finite difference approximations on a spatial grid or through restriction of the continuous operator to a finite dimensional subspace. In the latter ``finite element" case, the entries of ${\bf M}$ are inner products  of the respective basis functions for the finite dimensional space and these basis functions are usually chosen so that few entries in a typical row of ${\bf A}$ or ${\bf M}$ are nonzero. In structures problems ${\bf A}$ is called the ``stiffness'' matrix  and ${\bf M}$ is called the ``mass'' matrix.  In chemistry and physics ${\bf M}$ is     often referred to as the ``overlap'' matrix. A nice feature of finite element approach to discretization is that boundary conditions are naturally incorporated into the discrete problem. Moreover, in the self-adjoint  case, the Rayleigh principle is preserved from the continuous to the discrete problem. In particular, since Ritz values are Rayleigh quotients, this assures the smallest Ritz value is greater than or equal to the smallest eigenvalue of the original problem.

Basis functions that provide sparsity are usually not orthogonal in the natural inner product and hence, ${\bf M}$ is usually not diagonal. Thus it is typical for large scale eigenproblems to arise as generalized rather than standard problems with ${\bf M}$ symmetric and positive semi-definite. The matrix ${\bf A}$ is generally symmetric when the underlying continuous operator is self-adjoint and non-symmetric otherwise. There are a number of ways to convert the generalized problem to standard form. There is always motivation to preserve symmetry when it is present.

The simplest direct conversion to a standard problem is through factorization of ${\bf M}$.If ${\bf M}$ is positive definite then factor and the eigenvalues of are the eigenvalues of and the eigenvectors are obtained by solving where is an eigenvector of . This standard transformation is fine if one wants the eigenvalues of largest magnitude and it preserves symmetry if ${\bf A}$ is symmetric. However, when ${\bf M}$ is ill-conditioned  this can be a dangerous transformation leading to numerical difficulties. Since a matrix factorization will have to be done anyway, one may as well formulate a spectral transformation.



 
next up previous contents index
Next: Structure of the Spectral Up: The Implicitly Restarted Arnoldi Previous: Block Methods
Chao Yang
11/7/1997