Error analysis of the Lanczos algorithm for the nonsymmetric eigenvalue problem
HTML articles powered by AMS MathViewer
- by Zhaojun Bai PDF
- Math. Comp. 62 (1994), 209-226 Request permission
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
-
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.
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.
- Daniel L. Boley, Sylvan Elhay, Gene H. Golub, and Martin H. Gutknecht, Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights, Numer. Algorithms 1 (1991), no. 1, 21–43. MR 1135286, DOI 10.1007/BF02145581
- Jane K. Cullum and Ralph A. Willoughby, Lanczos algorithms for large symmetric eigenvalue computations. Vol. 1, Classics in Applied Mathematics, vol. 41, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. Theory; Reprint of the 1985 original [Birkhäuser Boston, Boston, MA; MR0808962 (87h:65064a)]. MR 1948689, DOI 10.1137/1.9780898719192
- Jane Cullum and Ralph A. Willoughby, A practical procedure for computing eigenvalues of large sparse nonsymmetric matrices, Large scale eigenvalue problems (Oberlech, 1985) North-Holland Math. Stud., vol. 127, North-Holland, Amsterdam, 1986, pp. 193–240. MR 875438, DOI 10.1016/S0304-0208(08)72647-1
- Ernest R. Davidson, Super-matrix methods, Comput. Phys. Comm. 53 (1989), no. 1-3, 49–60. Practical iterative methods for large scale computations (Minneapolis, MN, 1988). MR 1004696, DOI 10.1016/0010-4655(89)90147-1 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.
- Thomas Ericsson and Axel Ruhe, Lánczos algorithms and field of value rotations for symmetric matrix pencils, Linear Algebra Appl. 88/89 (1987), 733–746. MR 882469, DOI 10.1016/0024-3795(87)90132-7 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.
- William B. Gragg, Matrix interpretations and applications of the continued fraction algorithm, Rocky Mountain J. Math. 4 (1974), 213–225. MR 341830, DOI 10.1216/RMJ-1974-4-2-213 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.
- G. H. Golub and T. N. Robertson, A generalized Bairstow algorithm, Comm. ACM 10 (1967), 371–373. MR 0240970, DOI 10.1145/363332.363376
- G. H. Golub and J. H. Wilkinson, Ill-conditioned eigensystems and the computation of the Jordan canonical form, SIAM Rev. 18 (1976), no. 4, 578–619. MR 413456, DOI 10.1137/1018113
- 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
- A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl. 113 (1989), 7–63. MR 978581, DOI 10.1016/0024-3795(89)90285-1 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. N. J. Higham, Algorithm 694: A Collection of Test Matrices in MATLAB, ACM Trans. Math. Software 17 (1991), 289-305.
- W. Kahan, B. N. Parlett, and E. Jiang, Residual bounds on approximate eigensystems of nonnormal matrices, SIAM J. Numer. Anal. 19 (1982), no. 3, 470–484. MR 656463, DOI 10.1137/0719030
- Cornelius Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards 45 (1950), 255–282. MR 0042791
- C. C. Paige, Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix, J. Inst. Math. Appl. 18 (1976), no. 3, 341–349. MR 501834
- C. C. Paige, Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem, Linear Algebra Appl. 34 (1980), 235–258. MR 591433, DOI 10.1016/0024-3795(80)90167-6
- Beresford Parlett, Laguerre’s method applied to the matrix eigenvalue problem, Math. Comp. 18 (1964), 464–485. MR 165668, DOI 10.1090/S0025-5718-1964-0165668-2
- B. N. Parlett and D. S. Scott, The Lanczos algorithm with selective orthogonalization, Math. Comp. 33 (1979), no. 145, 217–238. MR 514820, DOI 10.1090/S0025-5718-1979-0514820-3
- 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, DOI 10.1016/0024-3795(80)90248-7
- 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, 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
- Beresford N. Parlett, Reduction to tridiagonal form and minimal realizations, SIAM J. Matrix Anal. Appl. 13 (1992), no. 2, 567–593. MR 1152769, DOI 10.1137/0613036
- Axel Ruhe, Rational Krylov sequence methods for eigenvalue computation, Linear Algebra Appl. 58 (1984), 391–405. MR 739296, DOI 10.1016/0024-3795(84)90221-0
- Pavel Raschman, Milan Kubíček, and Miloš Marek, Waves in distributed chemical systems: experiments and computations, New approaches to nonlinear problems in dynamics (Proc. Conf., Pacific Grove, Calif., 1979) SIAM, Philadelphia, Pa., 1980, pp. 271–288. MR 584593
- Horst D. Simon, Analysis of the symmetric Lanczos algorithm with reorthogonalization methods, Linear Algebra Appl. 61 (1984), 101–131. MR 755252, DOI 10.1016/0024-3795(84)90025-9
- 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, 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
- 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
- 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 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.
- 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
- A. Greenbaum and Z. Strakoš, Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl. 13 (1992), no. 1, 121–137. MR 1146656, DOI 10.1137/0613011
- J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
Additional Information
- © Copyright 1994 American Mathematical Society
- Journal: Math. Comp. 62 (1994), 209-226
- MSC: Primary 65F15
- DOI: https://doi.org/10.1090/S0025-5718-1994-1201066-7
- MathSciNet review: 1201066