     Next: Software Availability Up: Practical Algorithm Previous: Deflation.   Contents   Index

Restarting a Block Arnoldi Reduction.

In §7.6, we motivated and explained how to implicitly restart the Arnoldi method. The experimental results in [292,290,24] show that an implicitly restarted scheme is superior to other block methods that have appeared in the literature [391,398]. These explicit restarting techniques select a subsequent starting block based on some criterion and then restart from scratch. Not only does BIRAM use dramatically fewer matrix-vector products; it also requires significantly fewer Arnoldi vectors to be stored. The reader is referred to [391,227,245,398] for information on explicitly restarted Arnoldi methods.

The extension of the scheme in §7.6 within a block Arnoldi method is straightforward. The chief difference is that an implicitly shifted QR algorithm that retains band Hessenberg form is needed. As with the standard implicitly shifted QR algorithm, a sequence of unitary matrices are constructed and applied so that an updated band Hessenberg matrix results.

Numerous choices are possible for the selection of the shifts used during the QR algorithm, including the specific choice of If the shifts are in complex conjugate pairs, the implicit double shift [198, pp. 355-358] can be used to avoid complex arithmetic.

Typically, the shifts are selected by utilizing the spectral information contained in . Partition the eigenvalues of so that (137)

For an unblocked reduction, the shifts are selected from the unwanted eigenvalues of where Sorensen  proposed this as an exact shift strategy. This strategy is equivalent to restarting the subsequent reduction with a linear combination of the approximate Schur vectors associated with the wanted eigenvalues. Other interesting strategies include the roots of Chebyshev polynomials , harmonic Ritz values [331,337,349,411], the roots of Leja polynomials , the roots of least squares polynomials , and refined shifts . In particular, the Leja and harmonic Ritz values have been used to estimate the interior eigenvalues of .

In Algorithm 7.12, the integer is typically set to , the number of wanted eigenvalues, during the input step. Once the iteration loop has been entered, the values of , , and thus may vary for every value of When , we cannot apply all unwanted eigenvalues as shifts. We are then faced with the question of selecting which shifts to apply and whether we should consider applying more than shifts.

For example, shifts can be applied until a Ritz pair satisfies the convergence tolerance. The Ritz pairs can then be deflated (or locked). (This is equivalent to the deflated iterative Arnoldi algorithm given by Saad [387, p. 181] and used in the implementations in [24,398].) This approach allows us to implicitly apply a polynomial filter of the maximum degree. (Application of more than shifts will require applying explicit polynomials in ) However, as more shifts are applied, the cost in computing the subsequent Arnoldi reduction increases.

A strategy that varies , (relative to ) and the shifts used during every iteration will give the best results. This is the subject of current research. The recent report  discusses an adaptive strategy for symmetric eigenvalue problems.     Next: Software Availability Up: Practical Algorithm Previous: Deflation.   Contents   Index
Susan Blackford 2000-11-20