A lookahead Lánczos algorithm for unsymmetric matrices
Authors:
Beresford N. Parlett, Derek R. Taylor and Zhishun A. Liu
Journal:
Math. Comp. 44 (1985), 105124
MSC:
Primary 65F15
MathSciNet review:
771034
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The twosided 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 pivot in triangular factorization whenever a 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 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.
 [1]
Chandler
Davis and W.
M. Kahan, The rotation of eigenvectors by a perturbation. III,
SIAM J. Numer. Anal. 7 (1970), 1–46. MR 0264450
(41 #9044)
 [2]
W. Gragg, Notes from a "Kentucky Workshop" on the moment problem and indefinite metrics.
 [3]
Alston
S. Householder, The theory of matrices in numerical analysis,
Blaisdell Publishing Co. Ginn and Co. New YorkTorontoLondon, 1964. MR 0175290
(30 #5475)
 [4]
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 (83h:65050), http://dx.doi.org/10.1137/0719030
 [5]
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
(13,163d)
 [6]
Beresford
Parlett, Laguerre’s method applied to the
matrix eigenvalue problem, Math. Comp. 18 (1964), 464–485.
MR
0165668 (29 #2948), http://dx.doi.org/10.1090/S00255718196401656682
 [7]
Beresford
N. Parlett, The symmetric eigenvalue problem, PrenticeHall,
Inc., Englewood Cliffs, N.J., 1980. PrenticeHall Series in Computational
Mathematics. MR
570116 (81j:65063)
 [8]
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 0305564
(46 #4694)
 [9]
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), http://dx.doi.org/10.1016/00243795(80)90169X
 [10]
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
(84g:65045), http://dx.doi.org/10.1137/0719031
 [11]
D. R. Taylor, Analysis of the Look Ahead Lanczos Algorithm, Ph.D. thesis, University of California, Berkeley, 1982.
 [12]
J.
H. Wilkinson, The algebraic eigenvalue problem, Clarendon
Press, Oxford, 1965. MR 0184422
(32 #1894)
 [1]
 C. Davis & W. Kahan, "The rotation of eigenvectors by a perturbationIII," SIAM J. Numer. Anal., v. 7, 1970, pp. 146. MR 0264450 (41:9044)
 [2]
 W. Gragg, Notes from a "Kentucky Workshop" on the moment problem and indefinite metrics.
 [3]
 A. S. Householder, The Theory of Matrices in Numerical Analysis, Blaisdell, New York, 1964. MR 0175290 (30:5475)
 [4]
 W. Kahan, B. N. Parlett & E. Jiang, "Residual bounds on approximate eigensystems of nonnormal matrices," SIAM J. Numer. Anal., v. 19, 1982, pp. 470484. MR 656463 (83h:65050)
 [5]
 C. Lanczos, "An iteration method for the solution of the eigenvalue problem of linear differential and integral operators," J. Res. Nat. Bur. Standards, v. 45, 1950, pp. 255282. See pp. 266270. MR 0042791 (13:163d)
 [6]
 B. N. Parlett, "Laguerre's method applied to the matrix eigenvalue problem," Math. Comp., v. 18, 1964, pp. 464487. MR 0165668 (29:2948)
 [7]
 B. N. Parlett, The Symmetric Eigenvalue Problem, PrenticeHall, Englewood Cliffs, N. J., 1980. MR 570116 (81j:65063)
 [8]
 B. N. Parlett & J. R. Bunch, "Direct methods for solving symmetric indefinite systems of linear equations," SIAM J. Numer. Anal., v. 8, 1971, pp. 639655. MR 0305564 (46:4694)
 [9]
 Y. Saad, "Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices," Linear Algebra Appl., v. 34, 1980, pp. 269295. MR 591435 (81m:65055)
 [10]
 Y. Saad, "The Lanczos biorthogonalization algorithm and other oblique projection methods for solving large unsymmetric eigenproblems," SIAM J. Numer. Anal., v. 19, 1982, pp. 484500. MR 656464 (84g:65045)
 [11]
 D. R. Taylor, Analysis of the Look Ahead Lanczos Algorithm, Ph.D. thesis, University of California, Berkeley, 1982.
 [12]
 J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford Univ. Press, Oxford, 1965. MR 0184422 (32:1894)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F15
Retrieve articles in all journals
with MSC:
65F15
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198507710342
PII:
S 00255718(1985)07710342
Article copyright:
© Copyright 1985
American Mathematical Society
