Low-rank modification of the unsymmetric Lanczos algorithm

Author:
Thomas Huckle

Journal:
Math. Comp. **64** (1995), 1577-1588

MSC:
Primary 65F10

DOI:
https://doi.org/10.1090/S0025-5718-1995-1312097-1

MathSciNet review:
1312097

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The unsymmetric Lanczos algorithm is an important method for eigenvalue estimation and for solving linear equations. Unfortunately, the algorithm may break down without providing useful information; this is referred to as a serious breakdown in the literature. Here, we introduce a low-rank modification of the original matrix *A* in the case of a serious breakdown. This modification can be used to cure a serious breakdown as long as we have orthogonality of the already computed Lanczos vectors. We can switch to a new rank-1 modified matrix such that

- the Lanczos algorithm has no serious breakdown in this step when applied on ,

- the already computed variables in the Lanczos algorithm for *A* and coincide,

- using a Lanczos-based iterative solver, e.g. BCG or QMR, with start vectors and , we have , and thus by continuing the Lanczos algorithm with we automatically get the desired solution .

Also, if the Lanczos vectors have lost their orthogonality, we show theoretically and by numerical examples that the modified Lanczos method has the same convergence behavior as the Lanczos method without breakdown. Thus, in the case of a serious breakdown we only have to compute the new rank-1 modified matrix and step further in the original algorithm now using .

**[1]**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**, https://doi.org/10.1016/S0304-0208(08)72647-1**[2]**Roland W. Freund, Gene H. Golub, and Noël M. Nachtigal,*Iterative solution of linear systems*, Acta numerica, 1992, Acta Numer., Cambridge Univ. Press, Cambridge, 1992, pp. 57–100. MR**1165723****[3]**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**, https://doi.org/10.1137/0914009**[4]**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**, https://doi.org/10.1007/BF01385726**[5]**R. Fletcher,*Conjugate gradient methods for indefinite systems*, Numerical analysis (Proc 6th Biennial Dundee Conf., Univ. Dundee, Dundee, 1975) Springer, Berlin, 1976, pp. 73–89. Lecture Notes in Math., Vol. 506. MR**0461857****[6]**M. H. Gutknecht,*The unsymmetric Lanczos algorithms and their relations to Padé approximation, continued fractions, and the QD algorithm*, Proc. Copper Mountain Conference on Iterative Methods, Computational Math Group, The University of Colorado at Denver, 1990.**[7]**W. D. Jaubert,*Generalized conjugate gradient and Lanczos methods for the solution of non-symmetric systems of linear equations*, Ph.D. Dissertation, University of Texas, Austin, TX, 1990.**[8]**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****[9]**Cornelius Lanczos,*Solution of systems of linear equations by minimized-iterations*, J. Research Nat. Bur. Standards**49**(1952), 33–53. MR**0051583****[10]**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**, https://doi.org/10.1016/0024-3795(80)90248-7**[11]**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**, https://doi.org/10.1090/S0025-5718-1985-0771034-2**[12]**Beresford N. Parlett,*Reduction to tridiagonal form and minimal realizations*, SIAM J. Matrix Anal. Appl.**13**(1992), no. 2, 567–593. MR**1152769**, https://doi.org/10.1137/0613036**[13]**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**, https://doi.org/10.1137/0719031**[14]**D. R. Taylor,*Analysis of the look ahead Lanczos algorithm*, Ph.D. Dissertation, University of California, Berkeley, CA, 1982.**[15]**Qiang Ye,*A breakdown-free variation of the nonsymmetric Lanczos algorithms*, Math. Comp.**62**(1994), no. 205, 179–207. MR**1201072**, https://doi.org/10.1090/S0025-5718-1994-1201072-2

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

Retrieve articles in all journals with MSC: 65F10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1995-1312097-1

Article copyright:
© Copyright 1995
American Mathematical Society