Mathematics of Computation

Author(s): Ronald B. Morgan.
Journal: Math. Comp. 65 (1996), 1213-1230.
MSC (1991): Primary 65F15, 15A18
Retrieve article in: PDF
This article is available free of charge

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.

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

Ronald B. Morgan
Affiliation: Department of Mathematics, Baylor University, Waco, Texas 76798-7328
Email: morganr@baylor.edu

DOI: 10.1090/S0025-5718-96-00745-4
PII: S 0025-5718(96)00745-4
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.
Copyright of article: Copyright 1996, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS