Next: Deflation and Stopping Rules Up: Implicitly Restarted Arnoldi Method Previous: Numerical Stability   Contents   Index

This implicit scheme costs rather than the matrix-vector products the explicit scheme would require to apply the same -degree polynomial and rebuild the -step Arnoldi factorization. When the operation is relatively expensive, this savings can be considerable. However, there are tradeoffs. It is impossible to predict optimal values for and in general. The distribution of the spectrum of has a great deal to do with convergence behavior. Two matrices with precisely the same sparsity pattern could exhibit completely different convergence characteristics for a given choice of and . Therefore, it would be misleading to draw any conclusions based solely on operation counts per iteration. Nevertheless, it can be useful to have a notion of the major costs of an iteration to guide initial choices.

In the following, we assume that the cost of a matrix-vector product is . For a sparse matrix, one could think of as twice the average number of nonzero entries per row of . For a dense matrix , and for an FFT matrix . See §10.2. For a fixed value of and , the cost (in floating point operations) for one iteration of IRAM is

1. matrix-vector products : ;

2. Arnoldi steps (extend from to ) : ;

3. orthogonalization corrections: roughly per correction. A worst-case estimate is (assumes one correction per each new Arnoldi vector);

4. implicit restarting: ;

5. total cost: .

Note that the factor of 2 in the second term is due to a worst-case scenario with respect to orthogonalization corrections. This factor will usually be around 1.5 in practice. If the matrix-vector product is cheap ( i.e. is quite small) then the cost of implicit restarting is significant and alternatives should be considered. One of these might be to use a polynomial spectral transformation. This would involve operating with a suitably constructed polynomial function of in place of . An example would be a Chebyshev polynomial designed to damp the unwanted portion of the spectrum. The action would, of course, be applied as a succession of matrix-vector products involving .

Next: Deflation and Stopping Rules Up: Implicitly Restarted Arnoldi Method Previous: Numerical Stability   Contents   Index
Susan Blackford 2000-11-20