A look-ahead Lánczos algorithm for unsymmetric matrices

Parlett, Beresford N.; Taylor, Derek R.; Liu, Zhishun A.

doi:10.1090/S0025-5718-1985-0771034-2

A look-ahead Lánczos algorithm for unsymmetric matrices
HTML articles powered by AMS MathViewer

by Beresford N. Parlett, Derek R. Taylor and Zhishun A. Liu PDF

Math. Comp. 44 (1985), 105-124 Request permission

Abstract:

The two-sided Lanczos algorithm sometimes suffers from serious breakdowns. These occur when the associated moment matrix does not permit triangular factorization. We modify the algorithm slightly so that it corresponds to using a $2 \times 2$ pivot in triangular factorization whenever a $1 \times 1$ pivot would be dangerous. The likelihood of breakdown is greatly reduced. The price paid is that the tridiagonal matrix produced by the algorithm now has bumps whenever a $2 \times 2$ pivot is used. Experiments with several versions of the algorithm on a variety of matrices are described, including some large problems arising in the study of plasma instability.

References

Chandler Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal. 7 (1970), 1–46. MR 264450, DOI 10.1137/0707001
Alston S. Householder, The theory of matrices in numerical analysis, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1964. MR 0175290
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, DOI 10.6028/jres.045.026
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
Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 570116
J. R. Bunch and B. N. Parlett, Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal. 8 (1971), 639–655. MR 305564, DOI 10.1137/0708060
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
Y. Saad, The Lanczos biorthogonalization algorithm and other oblique projection methods for solving large unsymmetric systems, SIAM J. Numer. Anal. 19 (1982), no. 3, 485–506. MR 656464, DOI 10.1137/0719031

Analysis of the Look Ahead Lanczos Algorithm

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