Basic Iterative Algorithms

Next: Cost Issues Up: Templates for Solution Previous: Available Operations

## Basic Iterative Algorithms

The following basic algorithms for sparse eigenproblems will be included.

• Simultaneous iteration methods

• Arnoldi methods

• Lanczos methods

• Davidson methods

• Refinement methods

• Trace minimization (self-adjoint case only)

This list is not exhaustive, and we are actively looking for other algorithms. Also, some common methods may classified in several ways. For example, simultaneous iteration and block Arnoldi with an immediate restart are identical. These categories are not meant to be mutually exclusive, but to be helpful to the user. We will include some older but commonly used methods, just to be able to advise the user to use more powerful alternatives, and for experimental purposes.

Arnoldi and Lanczos methods are Krylov subspaces based techniques. These methods may converge very fast in combination with shifted-and-inverted operators, which means that has to be used in matrix vector products in each iteration step. If only approximations for are available then Davidson's method can be used as an acceleration technique for the inexact shift-and-invert operations. Approximations for can be computed from a preconditioner for or by a few steps of a (preconditioned) iterative method [35].

Trace minimization is suitable for self-adjoint problems, and uses optimization techniques like conjugate gradients to find the smallest eigenvalues.

There is unfortunately no simple way to identify the best algorithm and choice of options to the user. The more the user discovers about the problem (such as approximate eigenvalues), the better a choice can be made. In the common situation where the user is solving a sequence of similar problems, this is quite important.

There is also unfortunately no inexpensive way to provide a guarantee that all eigenvalues in a region have been found, when the problem is not self-adjoint. For Hermitian eigenvalue problems by factoring certain translations of by the identity, it is possible to guarantee that all eigenvalues in a region have been found. In the non-Hermitian case, this same task is accomplished by a vastly more expensive technique called a Nyquist plot (i.e. compute the winding number). However, depending on the problem, there are methods to help increase one's confidence that all eigenvalues have been found.

Next: Cost Issues Up: Templates for Solution Previous: Available Operations

Jack Dongarra
Wed Jun 21 02:35:11 EDT 1995