Next: Variants Up: Arnoldi Method   Y. Saad Previous: Arnoldi Method   Y. Saad   Contents   Index

## Basic Algorithm

The Arnoldi method is an orthogonal projection method onto a Krylov subspace. It starts with the Arnoldi procedure as described in Algorithm 7.3. The procedure can be essentially viewed as a modified Gram-Schmidt process for building an orthogonal basis of the Krylov subspace .

The above procedure will stop if the vector computed in line (8) vanishes. The vectors form an orthonormal system by construction and are called Arnoldi vectors. An easy induction argument shows that this system is a basis of the Krylov subspace .

Next we consider a fundamental relation between quantities generated by the algorithm. The following equality is readily derived:

 (122)

If we denote by the matrix with column vectors , and by the Hessenberg matrix whose nonzero entries are defined by the algorithm, then the following relations hold:
 (123) (124)

Relation eq:VmTAVm follows from eq:AVm by multiplying both sides of eq:AVm by and making use of the orthonormality of .

As was noted earlier the algorithm breaks down when the norm of computed on line (8) vanishes at a certain step . As it turns out, this happens if and only if the starting vector is a combination of eigenvectors (i.e., the minimal polynomial of is of degree ). In addition, the subspace is then invariant and the approximate eigenvalues and eigenvectors are exact [387].

The approximate eigenvalues provided by the projection process onto are the eigenvalues of the Hessenberg matrix . These are known as Ritz values. A Ritz approximate eigenvector associated with a Ritz value is defined by , where is an eigenvector associated with the eigenvalue . A number of the Ritz eigenvalues, typically a small fraction of , will usually constitute good approximations for corresponding eigenvalues of , and the quality of the approximation will usually improve as increases.

The original algorithm consists of increasing until all desired eigenvalues of are found. For large matrices, this becomes costly both in terms of computation and storage. In terms of storage, we need to keep vectors of length plus an Hessenberg matrix, a total of approximately . For the arithmetic costs, we need to multiply by , at the cost of , where is number of nonzero elements in , and then orthogonalize the result against vectors at the cost of which increases with the step number . Thus an -dimensional Arnoldi procedure costs in storage and in arithmetic operations.

Obtaining the residual norm, for a Ritz pair, as the algorithm progresses is fairly inexpensive. Let be an eigenvector of associated with the eigenvalue , and let be the Ritz approximate eigenvector . We have the relation

and, therefore,

Thus, the residual norm is equal to the absolute value of the last component of the eigenvector multiplied by . The residual norms are not always indicative of actual errors in , but can be quite helpful in deriving stopping procedures.

Next: Variants Up: Arnoldi Method   Y. Saad Previous: Arnoldi Method   Y. Saad   Contents   Index
Susan Blackford 2000-11-20