On restarting the Arnoldi method for large nonsymmetric eigenvalue problems

Morgan, Ronald

doi:10.1090/S0025-5718-96-00745-4

On restarting the Arnoldi method for large nonsymmetric eigenvalue problems
HTML articles powered by AMS MathViewer

by Ronald B. Morgan PDF

Math. Comp. 65 (1996), 1213-1230 Request permission

Abstract:

The Arnoldi method computes eigenvalues of large nonsymmetric matrices. Restarting is generally needed to reduce storage requirements and orthogonalization costs. However, restarting slows down the convergence and makes the choice of the new starting vector difficult if several eigenvalues are desired. We analyze several approaches to restarting and show why Sorensen’s implicit QR approach is generally far superior to the others. Ritz vectors are combined in precisely the right way for an effective new starting vector. Also, a new method for restarting Arnoldi is presented. It is mathematically equivalent to the Sorensen approach but has additional uses.

References

C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
J. W. Daniel, W. B. Gragg, L. Kaufman, and G. W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt $QR$ factorization, Math. Comp. 30 (1976), no. 136, 772–795. MR 431641, DOI 10.1090/S0025-5718-1976-0431641-8
Ernest R. Davidson, The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices, J. Comput. Phys. 17 (1975), 87–94. MR 381271, DOI 10.1016/0021-9991(75)90065-0
I. S. Duff, R. G. Grimes, and J. G. Lewis, Sparse matrix test problems, ACM Trans. Math. Soft. 15 (1989), 1-14.
Thomas Ericsson and Axel Ruhe, The spectral transformation Lánczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. Comp. 35 (1980), no. 152, 1251–1268. MR 583502, DOI 10.1090/S0025-5718-1980-0583502-2
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
William J. Stewart and Alan Jennings, A simultaneous iteration algorithm for real matrices, ACM Trans. Math. Software 7 (1981), no. 2, 184–198. MR 618513, DOI 10.1145/355945.355948
R. B. Lehoucq, Analysis and Implementation of an Implicitly Restarted Arnoldi Iteration, Ph.D. thesis, Rice University, Houston, TX, 1995.
Ronald B. Morgan, Computing interior eigenvalues of large matrices, Linear Algebra Appl. 154/156 (1991), 289–309. MR 1113147, DOI 10.1016/0024-3795(91)90381-6
Ronald B. Morgan, Generalizations of Davidson’s method for computing eigenvalues of large nonsymmetric matrices, J. Comput. Phys. 101 (1992), no. 2, 287–291. MR 1174624, DOI 10.1016/0021-9991(92)90006-K
R. B. Morgan, A restarted GMRES method augmented with eigenvectors, SIAM J. Matrix Anal. Appl. 16 (1995), 1154-1171.
Ronald B. Morgan and David S. Scott, Generalizations of Davidson’s method for computing eigenvalues of sparse symmetric matrices, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 817–825. MR 848565, DOI 10.1137/0907054
B. Nour-Omid, B. N. Parlett, R. L. Taylor, Lanczos versus subspace iteration for solution of eigenvalue problems, Inter. J. Num. Meth. Eng. 19 (1983), 859-871.
Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 570116
Beresford N. Parlett and Youcef Saad, Complex shift and invert strategies for real matrices, Linear Algebra Appl. 88/89 (1987), 575–595. MR 882464, DOI 10.1016/0024-3795(87)90126-1
Beresford N. Parlett, Derek R. Taylor, and Zhishun A. Liu, A look-ahead Lánczos algorithm for unsymmetric matrices, Math. Comp. 44 (1985), no. 169, 105–124. MR 771034, DOI 10.1090/S0025-5718-1985-0771034-2
Bo Kȧgström and Axel Ruhe (eds.), Matrix pencils, Lecture Notes in Mathematics, vol. 973, Springer-Verlag, Berlin-New York, 1983. MR 697741
Youcef Saad, Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems, Math. Comp. 42 (1984), no. 166, 567–588. MR 736453, DOI 10.1090/S0025-5718-1984-0736453-8
Youcef Saad, Numerical methods for large eigenvalue problems, Algorithms and Architectures for Advanced Scientific Computing, Manchester University Press, Manchester; Halsted Press [John Wiley & Sons, Inc.], New York, 1992. MR 1177405
Youcef Saad, Numerical solution of large nonsymmetric eigenvalue problems, Comput. Phys. Comm. 53 (1989), no. 1-3, 71–90. Practical iterative methods for large scale computations (Minneapolis, MN, 1988). MR 1004697, DOI 10.1016/0010-4655(89)90149-5
Y. Saad, On the rates of convergence of the Lanczos and the block-Lanczos methods, SIAM J. Numer. Anal. 17 (1980), no. 5, 687–706. MR 588755, DOI 10.1137/0717059
Y. Saad, Variations on Arnoldi’s method for computing eigenelements of large unsymmetric matrices, Linear Algebra Appl. 34 (1980), 269–295. MR 591435, DOI 10.1016/0024-3795(80)90169-X
Youcef Saad and Martin H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 856–869. MR 848568, DOI 10.1137/0907058
D. C. Sorensen, Implicit application of polynomial filters in a $k$-step Arnoldi method, SIAM J. Matrix Anal. Appl. 13 (1992), no. 1, 357–385. MR 1146670, DOI 10.1137/0613025
J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422