Error analysis of the Lanczos algorithm for the nonsymmetric eigenvalue problem

Bai, Zhaojun

doi:10.1090/S0025-5718-1994-1201066-7

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

LAPACK user’s guide

A collection of test matrices for the large sparse nonsymmetric eigenvalue problem

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

Computing selected eigenvalues of sparse unsymmetric matrices using subspace iteration

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

An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices

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

Analyses of the Lanczos algorithm and of the approximation problem in Richardson’s method

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

A completed theory of the nonsymmetric Lanczos process and related algorithms

Algorithm 694

A Collection of Test Matrices in MATLAB

17

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

SRRIT—A FORTRAN subroutine to calculate the dominant invariant subspace of a nonsymmetric matrix

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