A breakdown-free variation of the nonsymmetric Lanczos algorithms

Author:
Qiang Ye

Journal:
Math. Comp. **62** (1994), 179-207

MSC:
Primary 65F15

DOI:
https://doi.org/10.1090/S0025-5718-1994-1201072-2

MathSciNet review:
1201072

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

**[1]**W. E. Arnoldi,*The principle of minimized iterations in the solution of the matrix eigenvalue problem*, Quart. Appl. Math.**9**(1951), 17-29. MR**0042792 (13:163e)****[2]**D. Boley and G. Golub,*The nonsymmetric Lanczos algorithm and controllability*, Systems Control Lett.**16**(1991), 97-105. MR**1095250 (92e:93004)****[3]**D. Boley, S. Elhay, G. Golub, and M. Gutknecht,*Nonsymmetric Lanczos algorithms and finding orthogonal polynomials associated with indefinite weights*, Numerical Algorithms**1**(1991), 21-43. MR**1135286 (93f:65033)****[4]**C. Brezinski, M. Redivo Zaglia, and H. Sadok,*Avoiding breakdown and near-breakdown in Lanczos type algorithms*, Numerical Algorithms**1**(1991), 261-284. MR**1135297 (92j:65041)****[5]**J. Cullum, W. Kerner, and R. Willoughby,*A generalized nonsymmetric Lanczos procedure*, Comput. Phys. Comm.**53**(1989), 19-48. MR**1004695 (90h:65057)****[6]**J. Cullum and R. A. Willoughby,*Lanczos algorithms for large symmetric eigenvalue computations*, Birkhäuser, Boston, 1985.**[7]**R. Freund,*Krylov subspace methods for complex non-hermitian linear systems*, RIACS Report 91.11, NASA Ames Research Center, May 1991.**[8]**R. Freund, M. Gutknecht, and N. Nachtigal,*An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices*, SIAM J. Sci. Statist. Comput.**14**(1993), 137-158. MR**1201315 (93h:65048)****[9]**R. Freund and N. Nachtigal,*QMR*:*a quasi-minimal residual method for non-Hermitian linear systems*, Numer Math.**60**(1991), 315-339. MR**1137197 (92g:65034)****[10]**M. Gutknecht,*A completed theory of the unsymmetric Lanczos process and related algorithms*, part I, SIAM J. Matrix Anal. Appl.**13**(1992), 594-639. MR**1152770 (93e:65053)****[11]**-,*A completed theory of the unsymmetric Lanczos process and related algorithms*, part II, SIAM J. Matrix Anal. Appl. (to appear)**[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]**G. A. Geist,*Reduction of a general matrix to tridiagonal form*, SIAM J. Matrix Anal. Appl.**12**(1991), 362-373. MR**1089165 (91m:65104)****[14]**R. T. Gregory and D. L. Karney,*A collection of matrices for testing computational algorithms*, Robert E. Krieger Publishing Company, Huntington, NY, 1978. MR**515277 (80a:65089)****[15]**G. H. Golub and C. F. Van Loan,*Matrix computations*, The Johns Hopkins University Press, Baltimore, MD, 1983. MR**733103 (85h:65063)****[16]**W. D. Joubert,*Lanczos methods for the solution of nonsymmetric systems of linear equations*, SIAM J. Matrix Anal. Appl.**13**(1992), 926-943. MR**1168086 (93e:65054)****[17]**A. Dax and S. Kaniel,*The ELR method for computing the eigenvalues of a general matrix*, SIAM J. Numer. Anal.**18**(1981), 597-605. MR**622696 (82f:65037)****[18]**W. Kerner,*Large-scale complex eigenvalue problems*, J. Comput. Phys.**85**(1989), 1-85. MR**1025411 (90k:65103)****[19]**C. Lanczos,*An iteration method for the solution of the eigenvalue problem of linear differential and integral operators*, J. Res. Nat. Bur. Standards**45**(1950), 255-282. MR**0042791 (13:163d)****[20]**P. Lancaster and Q. Ye,*Rayleigh-Ritz and Lanczos methods for symmetric matrix pencils*, Linear Algebra Appl.**185**(1993), 173-201. MR**1213178 (94i:65050)****[21]**B. N. Parlett,*The symmetric eigenvalue problem*, Prentice-Hall, Englewood Cliffs, NJ, 1980. MR**570116 (81j:65063)****[22]**-,*Reduction to tridiagonal form and minimal realizations*, SIAM J. Matrix Anal. Appl.**13**(1992), 567-593. MR**1152769 (93c:65059)****[23]**B. N. Parlett, D. R. Taylor, and Z. A. Liu,*A look-ahead Lanczos algorithm for unsymmetric matrices*, Math. Comp.**44**(1985), 105-124. MR**771034 (86f:65072)****[24]**B. N. Parlett and H. C. Chen,*Use of an indefinite inner product for computing damped natural modes*, Linear Algebra Appl.**140**(1990), 53-88. MR**1075543 (92b:65030)****[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. MR**591435 (81m:65055)****[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. MR**0184422 (32:1894)****[29]**Q. Ye,*Variational principles and numerical algorithms for symmetric matrix pencils*, Ph.D. thesis, University of Calgary, Calgary, 1989.**[30]**-,*A convergence analysis of nonsymmetric Lanczos algorithms*, Math. Comp.**56**(1991), 677-691. MR**1068826 (91m:65115)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F15

Retrieve articles in all journals with MSC: 65F15

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1994-1201072-2

Keywords:
Lanczos algorithms,
breakdown,
nonsymmetric eigenvalue problems,
new-start procedure,
convergence

Article copyright:
© Copyright 1994
American Mathematical Society