×

zbMATH — the first resource for mathematics

A breakdown-free variation of the nonsymmetric Lanczos algorithms. (English) Zbl 0796.65046
In this variation of the nonsymmetric Lanczos algorithm, the author devises a method to obtain a gradual transition of the nonsymmetric, look-ahead Lanczos process and the Arnoldi algorithm. The Arnoldi algorithm is the most stable of these due to the use of orthogonal bases in the Krylov subspace, albeit at the cost of reduction to a full Hessenberg matrix, while the ordinary Lanczos reduces to a tridiagonal matrix by using dual or bi-orthogonal bases in two Krylov (left and right) subspaces.
Here we have the possibility of choosing a in-between stability and cost, and reducing to a banded Hessenberg matrix, by adding a new diagonal band each time when (near) breakdown occurs. The paper is completed with a priori error estimates and some numerical examples.

MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
Software:
na1
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] W. E. Arnoldi, The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quart. Appl. Math. 9 (1951), 17 – 29. · Zbl 0042.12801
[2] Daniel Boley and Gene Golub, The nonsymmetric Lanczos algorithm and controllability, Systems Control Lett. 16 (1991), no. 2, 97 – 105. · Zbl 0732.93004
[3] 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. · Zbl 0752.65010
[4] 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. · Zbl 0748.65033
[5] 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). · Zbl 0798.65050
[6] J. Cullum and R. A. Willoughby, Lanczos algorithms for large symmetric eigenvalue computations, Birkhäuser, Boston, 1985. · Zbl 0574.65028
[7] R. Freund, Krylov subspace methods for complex non-hermitian linear systems, RIACS Report 91.11, NASA Ames Research Center, May 1991. · Zbl 0744.65027
[8] 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. · Zbl 0770.65022
[9] 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. · Zbl 0754.65034
[10] 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. · Zbl 0760.65039
[11] -, A completed theory of the unsymmetric Lanczos process and related algorithms, part II, SIAM J. Matrix Anal. Appl. (to appear) · Zbl 0809.65028
[12] -, The unsymmetric Lanczos algorithms and their relations to Padé approximation, continued fraction and the qd algorithm, Preliminary Proceedings of the Copper Mountain Conference on Iterative Methods.
[13] George A. Geist, Reduction of a general matrix to tridiagonal form, SIAM J. Matrix Anal. Appl. 12 (1991), no. 2, 362 – 373. · Zbl 0725.65039
[14] 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. · Zbl 0395.65007
[15] 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. · Zbl 0559.65011
[16] 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). · Zbl 0758.65026
[17] 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. · Zbl 0472.65035
[18] W. Kerner, Large-scale complex eigenvalue problems, J. Comput. Phys. 85 (1989), no. 1, 1 – 85. · Zbl 0685.65028
[19] 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.
[20] Peter Lancaster and Qiang Ye, Rayleigh-Ritz and Lanczos methods for symmetric matrix pencils, Linear Algebra Appl. 185 (1993), 173 – 201. · Zbl 0771.65017
[21] Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. Prentice-Hall Series in Computational Mathematics. · Zbl 0431.65017
[22] Beresford N. Parlett, Reduction to tridiagonal form and minimal realizations, SIAM J. Matrix Anal. Appl. 13 (1992), no. 2, 567 – 593. · Zbl 0754.65040
[23] 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. · Zbl 0564.65022
[24] B. N. Parlett and H. C. Chen, Use of indefinite pencils for computing damped natural modes, Linear Algebra Appl. 140 (1990), 53 – 88. · Zbl 0725.65055
[25] C. C. Paige, The computation of eigenvalues and eigenvectors of very large sparse matrices, Ph.D. thesis, London University, London, 1971.
[26] Y. Saad, Variations on Arnoldi’s method for computing eigenelements of large unsymmetric matrices, Linear Algebra Appl. 34 (1980), 269 – 295. · Zbl 0456.65017
[27] D. R. Taylor, Analysis of the look ahead Lanczos algorithm, Ph.D. thesis, University of California, Berkeley, 1982.
[28] J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. · Zbl 0258.65037
[29] Q. Ye, Variational principles and numerical algorithms for symmetric matrix pencils, Ph.D. thesis, University of Calgary, Calgary, 1989.
[30] Qiang Ye, A convergence analysis for nonsymmetric Lanczos algorithms, Math. Comp. 56 (1991), no. 194, 677 – 691. · Zbl 0780.65025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.