Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Error analysis of the Lanczos algorithm for the nonsymmetric eigenvalue problem


Author: Zhaojun Bai
Journal: Math. Comp. 62 (1994), 209-226
MSC: Primary 65F15
DOI: https://doi.org/10.1090/S0025-5718-1994-1201066-7
MathSciNet review: 1201066
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents an error analysis of the Lanczos algorithm in finite-precision arithmetic for solving the standard nonsymmetric eigenvalue problem, if no breakdown occurs. An analog of Paige's theory on the relationship between the loss of orthogonality among the Lanczos vectors and the convergence of Ritz values in the symmetric Lanczos algorithm is discussed. The theory developed illustrates that in the nonsymmetric Lanczos scheme, if Ritz values are well conditioned, then the loss of biorthogonality among the computed Lanczos vectors implies the convergence of a group of Ritz triplets in terms of small residuals. Numerical experimental results confirm this observation.


References [Enhancements On Off] (What's this?)

  • [1] E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. Mckenney, S. Ostrouchov, and D. Sorensen, LAPACK user's guide, SIAM, Philadelphia, PA, 1992.
  • [2] Z. Bai, A collection of test matrices for the large sparse nonsymmetric eigenvalue problem, University of Kentucky, Department of Mathematics, RR-93-03. Aug. 1993.
  • [3] D. Boley, S. Elhay, G. H. Golub, and M. H. Gutknecht, Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights, Numerical Analysis Report NA-90-09, Stanford, Aug. 1990. MR 1135286 (93f:65033)
  • [4] J. Cullum and R. A. Willoughby, Lanczos algorithms for large symmetric eigenvalue computations, Vol. 1, Theory, Vol. 2, Programs; Birkhäuser, Basel, 1985. MR 1948689 (2003i:65003)
  • [5] -, A practical procedure for computing eigenvalues of large sparse nonsymmetric matrices, Large Scale Eigenvalue Problems (J. Cullum and R. A. Willoughby, eds.), North-Holland, Amsterdam, 1986, pp. 193-240. MR 875438 (88a:65040)
  • [6] E. R. Davidson, Super-matrix methods, Comput. Phys. Comm. 53 (1989), 49-60. MR 1004696 (90k:65101)
  • [7] I. S. Duff and J. A. Scott, Computing selected eigenvalues of sparse unsymmetric matrices using subspace iteration, RAL-91-056, Rutherford Appleton Laboratory, Oxon, England, 1991.
  • [8] T. Ericsson and A. Ruhe, Lanczos algorithms and field of value rotations for symmetric matrix pencils, Linear Algebra Appl. 88/89 (1987), pp. 733-746. MR 882469 (88f:65056)
  • [9] R. W. Freund, M. H. Gutknecht, and N. M. Nachtigal, An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, Part I, Tech. Rep. 90.45, RIACS, NASA Ames Research Center, Nov. 1990.
  • [10] W. B. Gragg, Matrix interpretations and applications of the continued fraction algorithm, Rocky Mountain J. Math. 5 (1974), 213-225. MR 0341830 (49:6576)
  • [11] J. Grcar, Analyses of the Lanczos algorithm and of the approximation problem in Richardson's method, Ph.D. Thesis, Univ. of Illinois at Urbana-Champaign, 1981.
  • [12] G. H. Golub and T. N. Robertson, A generalized Bairstow algorithm, Comm. ACM 10 (1967), 371-373. MR 0240970 (39:2315)
  • [13] G. H. Golub and J. H. Wilkinson, Ill-conditioned eigensystems and the computation of the Jordan canonical form, SIAM Rev. 18 (1976), 578-619. MR 0413456 (54:1570)
  • [14] G. H. Golub and C. F. Van Loan, Matrix computations, 2nd ed., The Johns Hopkins Univ. Press, Baltimore, MD, 1989. MR 1002570 (90d:65055)
  • [15] A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl. 113 (1989), 7-63. MR 978581 (90e:65044)
  • [16] M. H. Gutknecht, A completed theory of the nonsymmetric Lanczos process and related algorithms. Part I, II, IPS Res. Rep. No. 90-10, Zürich, 1990.
  • [17] N. J. Higham, Algorithm 694: A Collection of Test Matrices in MATLAB, ACM Trans. Math. Software 17 (1991), 289-305.
  • [18] W. Kahan, B. N. Parlett, and E. Jiang, Residual bounds on approximate eigensystems of nonnormal matrices, SIAM J. Numer. Anal. 19 (1982), 470-484. MR 656463 (83h:65050)
  • [19] C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Standards 45 (1950), 255-282. MR 0042791 (13:163d)
  • [20] C. Paige, Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix, J. Inst. Math. Appl. 18 (1976), 341-349. MR 0501834 (58:19082)
  • [21] -, Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem, Linear Algebra Appl. 34 (1980), 235-258. MR 591433 (82b:65025)
  • [22] B. N. Parlett, Laguerre's method applied to the matrix eigenvalue problem, Math. Comp. 18 (1964), 464-485. MR 0165668 (29:2948)
  • [23] B. N. Parlett and D. S. Scott, The Lanczos algorithm with selective reorthogonalization, Math. Comp. 33 (1979), 217-238. MR 514820 (80c:65090)
  • [24] B. N. Parlett, A new look at the Lanczos algorithm for solving symmetric systems of linear equations, Linear Algebra Appl. 29 (1980), 323-346. MR 562767 (83e:65064)
  • [25] -, The symmetric eigenvalue problem, Prentice-Hall, Englewood Cliffs, NJ, 1980. MR 570116 (81j:65063)
  • [26] B. N. Parlett, D. R. Taylor, and Z. Liu, A look-ahead Lanczos algorithm for unsymmetric matrices, Math. Comp. 44 (1985), 105-124. MR 771034 (86f:65072)
  • [27] B. N. Parlett, Reduction to tridiagonal form and minimal realizations, SIAM J. Math. Anal. Appl. 13 (1992), 567-593. MR 1152769 (93c:65059)
  • [28] A. Ruhe, Rational Krylov sequence methods for eigenvalue computation, Linear Algebra Appl. 58 (1984), 391-405. MR 739296 (85c:65043)
  • [29] P. Raschman, M. Kubicek, and M. Maros, Waves in distributed chemical systems: experiments and computations, New Approaches to Nonlinear Problems in Dynamics--Proc. Asilomar Conf. Ground, Pacific Grove, California, 1979 (P. J. Holmes, ed.), The Engineering Foundation, SIAM, Philadelphia, PA, 1980, pp. 271-288. MR 584593 (82b:80023)
  • [30] H. Simon, Analysis of the symmetric Lanczos algorithm with reorthogonalization methods, Linear Algebra Appl. 61 (1984), 101-131. MR 755252 (85k:65033)
  • [31] Y. Saad, Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices, Linear Algebra Appl. 34 (1980), 269-295. MR 591435 (81m:65055)
  • [32] -, Numerical solution of large nonsymmetric eigenvalue problems, Comput. Phys. Comm. 53 (1989), 71-90. MR 1004697 (90f:65064)
  • [33] -, Numerical methods for large eigenvalue problems, Halsted Press, Div. of John Wiley & Sons, Inc., New York, 1992. MR 1177405 (93h:65052)
  • [34] D. C. Sorensen, Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl. 13 (1992), 357-385. MR 1146670 (92i:65076)
  • [35] G. W. Stewart, SRRIT--A FORTRAN subroutine to calculate the dominant invariant subspace of a nonsymmetric matrix, University of Maryland, Department of Computer Science, TR-514, 1978.
  • [36] W. J. Stewart and A. Jennings, A simultaneous iteration algorithm for real matrices, ACM Trans. Math. Software 7 (1981), 184-198. MR 618513 (83d:65118)
  • [37] Z. Strakos and A. Greenbaum, Open questions in the convergence analysis of the Lanczos process for the real symmetric eigenvalue problem, IMA, University of Minnesota, IMA preprint 924, 1992. MR 1146656 (92j:65043)
  • [38] J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Oxford, 1965. MR 0184422 (32:1894)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F15

Retrieve articles in all journals with MSC: 65F15


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1994-1201066-7
Keywords: Nonsymmetric matrices, eigenvalue problem, error analysis, Lanczos method
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society