A breakdown-free variation of the nonsymmetric Lanczos algorithms

Ye, Qiang

doi:10.1090/S0025-5718-1994-1201072-2

A breakdown-free variation of the nonsymmetric Lanczos algorithms
HTML articles powered by AMS MathViewer

by Qiang Ye PDF

Math. Comp. 62 (1994), 179-207 Request permission

Abstract:

The nonsymmetric Lanczos tridiagonalization algorithm is essentially the Gram-Schmidt biorthogonalization method for generating biorthogonal bases of a pair of Krylov subspaces. It suffers from breakdown and instability when a pivot at some step is zero or nearly zero, which is often the result of mismatch of the two Krylov subspaces. In this paper, we propose to modify one of the two Krylov subspaces by introducing a "new-start" vector when a pivot is small. This new-start vector generates another Krylov subspace, which we add to the old one in an appropriate way so that the Gram-Schmidt method for the modified subspaces yields a recurrence similar to the Lanczos algorithm. Our method enforces the pivots to be above a certain threshold and can handle both exact breakdown and near-breakdown. In particular, we recover look-ahead Lanczos algorithms and Arnoldi’s algorithm as two special cases. We also discuss theoretical and practical issues concerning the new-start procedure and present a convergence analysis as well as some numerical examples.

References

W. E. Arnoldi, The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quart. Appl. Math. 9 (1951), 17–29. MR 42792, DOI 10.1090/S0033-569X-1951-42792-9
Daniel Boley and Gene Golub, The nonsymmetric Lanczos algorithm and controllability, Systems Control Lett. 16 (1991), no. 2, 97–105. MR 1095250, DOI 10.1016/0167-6911(91)90003-W
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
C. Brezinski, M. Redivo Zaglia, and H. Sadok, Avoiding breakdown and near-breakdown in Lanczos type algorithms, Numer. Algorithms 1 (1991), no. 3, 261–284. MR 1135297, DOI 10.1007/BF02142326
Jane Cullum, Wolfgang Kerner, and Ralph Willoughby, A generalized nonsymmetric Lanczos procedure, Comput. Phys. Comm. 53 (1989), no. 1-3, 19–48. Practical iterative methods for large scale computations (Minneapolis, MN, 1988). MR 1004695, DOI 10.1016/0010-4655(89)90146-X

Lanczos algorithms for large symmetric eigenvalue computations

Krylov subspace methods for complex non-hermitian linear systems

Roland W. Freund, Martin H. Gutknecht, and Noël M. Nachtigal, An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, SIAM J. Sci. Comput. 14 (1993), no. 1, 137–158. MR 1201315, DOI 10.1137/0914009
Roland W. Freund and Noël M. Nachtigal, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math. 60 (1991), no. 3, 315–339. MR 1137197, DOI 10.1007/BF01385726
Martin H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms. I, SIAM J. Matrix Anal. Appl. 13 (1992), no. 2, 594–639. MR 1152770, DOI 10.1137/0613037

A completed theory of the unsymmetric Lanczos process and related algorithms

The unsymmetric Lanczos algorithms and their relations to Padé approximation, continued fraction and the qd algorithm

George A. Geist, Reduction of a general matrix to tridiagonal form, SIAM J. Matrix Anal. Appl. 12 (1991), no. 2, 362–373. MR 1089165, DOI 10.1137/0612026
Robert T. Gregory and David L. Karney, A collection of matrices for testing computational algorithms, Robert E. Krieger Publishing Co., Huntington, N.Y., 1978. Corrected reprint of the 1969 edition. MR 515277
Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
Wayne Joubert, Lanczos methods for the solution of nonsymmetric systems of linear equations, SIAM J. Matrix Anal. Appl. 13 (1992), no. 3, 926–943. Iterative methods in numerical linear algebra (Copper Mountain, CO, 1990). MR 1168086, DOI 10.1137/0613056
A. Dax and S. Kaniel, The ELR method for computing the eigenvalues of a general matrix, SIAM J. Numer. Anal. 18 (1981), no. 4, 597–605. MR 622696, DOI 10.1137/0718038
W. Kerner, Large-scale complex eigenvalue problems, J. Comput. Phys. 85 (1989), no. 1, 1–85. MR 1025411, DOI 10.1016/0021-9991(89)90200-3
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
Peter Lancaster and Qiang Ye, Rayleigh-Ritz and Lanczos methods for symmetric matrix pencils, Linear Algebra Appl. 185 (1993), 173–201. MR 1213178, DOI 10.1016/0024-3795(93)90212-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, Reduction to tridiagonal form and minimal realizations, SIAM J. Matrix Anal. Appl. 13 (1992), no. 2, 567–593. MR 1152769, DOI 10.1137/0613036
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
B. N. Parlett and H. C. Chen, Use of indefinite pencils for computing damped natural modes, Linear Algebra Appl. 140 (1990), 53–88. MR 1075543, DOI 10.1016/0024-3795(90)90222-X

The computation of eigenvalues and eigenvectors of very large sparse matrices

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

Analysis of the look ahead Lanczos algorithm

J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422

Variational principles and numerical algorithms for symmetric matrix pencils

Qiang Ye, A convergence analysis for nonsymmetric Lanczos algorithms, Math. Comp. 56 (1991), no. 194, 677–691. MR 1068826, DOI 10.1090/S0025-5718-1991-1068826-4