Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On Restarting the Arnoldi Method for Large Nonsymmetric Eigenvalue Problems

Author: Ronald B. Morgan
Journal: Math. Comp. 65 (1996), 1213-1230
MSC (1991): Primary 65F15, 15A18
MathSciNet review: 1348046
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. W. E. Arnoldi, The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9 (1951), 17-29. MR 13:163e
  • 2. 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), 772-795. MR 55:4638
  • 3. E. 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 52:2168
  • 4. I. S. Duff, R. G. Grimes, and J. G. Lewis, Sparse matrix test problems, ACM Trans. Math. Soft. 15 (1989), 1-14.
  • 5. T. Ericsson and A. Ruhe, The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. Comp. 35 (1980), 1251-1268. MR 83b:65034
  • 6. G. H. Golub and C. F. Van Loan, Matrix Computations, 2nd ed., Johns Hopkins University Press, Baltimore, 1989. MR 90d:65055
  • 7. A. Jennings and W. J. Stewart, A simultaneous iteration algorithm for real matrices, ACM Trans. Math. Software 7 (1981), 184--198. MR 83d:65118
  • 8. R. B. Lehoucq, Analysis and Implementation of an Implicitly Restarted Arnoldi Iteration, Ph.D. thesis, Rice University, Houston, TX, 1995.
  • 9. R. B. Morgan, Computing interior eigenvalues of large matrices, Linear Algebra Appl. 154-156 (1991), 289-309. MR 92e:65050
  • 10. R. B. Morgan, Generalizations of Davidson's method for computing eigenvalues of large nonsymmetric matrices, J. Comput. Phys. 101 (1992), 287-291. MR 93e:65063
  • 11. R. B. Morgan, A restarted GMRES method augmented with eigenvectors, SIAM J. Matrix Anal. Appl. 16 (1995), 1154-1171. CMP 96:01
  • 12. R. B. Morgan and D. S. Scott, Generalizations of Davidson's method for computing eigenvalues of sparse symmetric matrices, SIAM J. Sci. Statist. Comput. 7 (1986), 817-825. MR 87g:65056
  • 13. 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.
  • 14. B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, N.J., 1980. MR 81j:65063
  • 15. B. N. Parlett and Y. Saad, Complex shift and invert strategies for real matrices, Linear Algebra Appl. 88/89 (1987), 575-595. MR 88d:65056
  • 16. B. N. Parlett, D. R. Taylor and Z. A. Liu, A look-ahead Lanczos algorithm for unsymmetric matrices, Math. Comp., vol. 44, 1985, pp. 105-124. MR 86f:65072
  • 17. A. Ruhe, Matrix pencils, Lecture Notes in Mathematics, No. 973, Springer Verlag, New York, 1983, pp. 104-120. MR 84c:65009
  • 18. Y. Saad, Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems, Math. Comp. 42 (1984), 567-588. MR 85i:65049
  • 19. Y. Saad, Numerical Methods for Large Eigenvalue Problems, Halsted Press, New York, NY, 1992. MR 93h:65052
  • 20. Y. Saad, Numerical solution of large nonsymmetric eigenvalue problems, Comput. Phys. Commun. 53 (1989), 71-90. MR 90f:65064
  • 21. Y. Saad, On the rates of convergence of the Lanczos and the block Lanczos methods, SIAM J. Numer. Anal. 17 (1980), 687-706. MR 82g:65022
  • 22. Y. Saad, Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices, Linear Algebra Appl. 34 (1980), 269-295. MR 81m:65055
  • 23. Y. Saad and M. H. Schultz, GMRES: a generalized minimum residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), 856-869. MR 87g:65064
  • 24. D. C. Sorensen, Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl. 13 (1992), 357-385. MR 92i:65076
  • 25. J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. MR 32:1894

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65F15, 15A18

Retrieve articles in all journals with MSC (1991): 65F15, 15A18

Additional Information

Ronald B. Morgan
Affiliation: Department of Mathematics, Baylor University, Waco, Texas 76798-7328

Keywords: Arnoldi, Krylov subspaces, eigenvalues, sparse matrices, nonsymmetric matrices
Received by editor(s): July 3, 1991
Received by editor(s) in revised form: March 19, 1993, November 22, 1994, and February 13, 1995
Additional Notes: This research was partially supported by the National Science Foundation under contract CCR-8910665.
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society