Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems

Author:
Youcef Saad

Journal:
Math. Comp. **42** (1984), 567-588

MSC:
Primary 65F15; Secondary 65F50

DOI:
https://doi.org/10.1090/S0025-5718-1984-0736453-8

MathSciNet review:
736453

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The present paper deals with the problem of computing a few of the eigenvalues with *largest (or smallest) real parts*, of a large sparse nonsymmetric matrix. We present a general acceleration technique based on Chebyshev polynomials and discuss its practical application to Arnoldi’s method and the subspace iteration method. The resulting algorithms are compared with the classical ones in a few experiments which exhibit a sharp superiority of the Arnoldi-Chebyshev approach.

- W. E. Arnoldi,
*The principle of minimized iteration in the solution of the matrix eigenvalue problem*, Quart. Appl. Math.**9**(1951), 17–29. MR**42792**, DOI https://doi.org/10.1090/S0033-569X-1951-42792-9 - Friedrich L. Bauer,
*Das Verfahren der Treppeniteration und verwandte Verfahren zur Lösung algebraischer Eigenwertprobleme*, Z. Angew. Math. Phys.**8**(1957), 214–235 (German). MR**88049**, DOI https://doi.org/10.1007/BF01600502
A. Clayton, - Maurice Clint and Alan Jennings,
*A simultaneous iteration method for the unsymmetric eigenvalue problem*, J. Inst. Math. Appl.**8**(1971), 111–121. MR**297116**
F. D’Almeida, - L. Meirovitch,
*A discussion of a paper by K. K. Gupta: “On a combined Sturm sequence and inverse iteration technique for eigenproblem solution of spinning structures” (Internat. J. Numer. Methods Engrg. 7 (1973), no. 4, 509–518)*, Internat. J. Numer. Methods Engrg.**9**(1975), no. 2, 488–491. With a reply by Gupta. MR**488842**, DOI https://doi.org/10.1002/nme.1620090216 - L. Meirovitch,
*A discussion of a paper by K. K. Gupta: “On a combined Sturm sequence and inverse iteration technique for eigenproblem solution of spinning structures” (Internat. J. Numer. Methods Engrg. 7 (1973), no. 4, 509–518)*, Internat. J. Numer. Methods Engrg.**9**(1975), no. 2, 488–491. With a reply by Gupta. MR**488842**, DOI https://doi.org/10.1002/nme.1620090216 - Louis A. Hageman and David M. Young,
*Applied iterative methods*, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1981. Computer Science and Applied Mathematics. MR**630192**
A. Jennings, "Eigenvalue methods and the analysis of structural vibration," In - A. Jennings and W. J. Stewart,
*Simultaneous iteration for partial eigensolution of real matrices*, J. Inst. Math. Appl.**15**(1975), 351–361. MR**408221** - William J. Stewart and Alan Jennings,
*A simultaneous iteration algorithm for real matrices*, ACM Trans. Math. Software**7**(1981), no. 2, 184–198. MR**618513**, DOI https://doi.org/10.1145/355945.355948
A. Jepson, - Samuel Karlin,
*Mathematical methods and theory in games, programming, and economics*, Dover Publications, Inc., New York, 1992. Vol. I: Matrix games, programming, and mathematical economics; Vol. II: The theory of infinite games; Reprint of the 1959 original. MR**1160778** - Linda Kaufman,
*Matrix methods for queueing problems*, SIAM J. Sci. Statist. Comput.**4**(1983), no. 3, 525–552. MR**723109**, DOI https://doi.org/10.1137/0904037
L. Kleinrock, - 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** - Alan J. Laub,
*Schur techniques for Riccati differential equations*, Feedback control of linear and nonlinear systems (Bielefeld/Rome, 1981) Lect. Notes Control Inf. Sci., vol. 39, Springer, Berlin, 1982, pp. 165–174. MR**837458**, DOI https://doi.org/10.1007/BFb0006827
T. A. Manteuffel, - Thomas A. Manteuffel,
*The Tchebychev iteration for nonsymmetric linear systems*, Numer. Math.**28**(1977), no. 3, 307–327. MR**474739**, DOI https://doi.org/10.1007/BF01389971 - Thomas A. Manteuffel,
*Adaptive procedure for estimating parameters for the nonsymmetric Tchebychev iteration*, Numer. Math.**31**(1978/79), no. 2, 183–208. MR**509674**, DOI https://doi.org/10.1007/BF01397475
B. Nour-Omid, B. N. Parlett & R. Taylor, - Beresford N. Parlett,
*The symmetric eigenvalue problem*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. Prentice-Hall Series in Computational Mathematics. MR**570116**
B. N. Parlett & D. Taylor, - Theodore J. Rivlin,
*The Chebyshev polynomials*, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR**0450850**
A. Ruhe, - Y. Saad,
*Variations on Arnoldi’s method for computing eigenelements of large unsymmetric matrices*, Linear Algebra Appl.**34**(1980), 269–295. MR**591435**, DOI https://doi.org/10.1016/0024-3795%2880%2990169-X
G. Sander, C. Bon & M. Geradin, "Finite element analysis of supersonic panel flutter," - D. H. Sattinger,
*Bifurcation of periodic solutions of the Navier-Stokes equations*, Arch. Rational Mech. Anal.**41**(1971), 66–80. MR**272257**, DOI https://doi.org/10.1007/BF00250178 - E. Seneta,
*Computing the stationary distribution for infinite Markov chains*, Linear Algebra Appl.**34**(1980), 259–267. MR**591434**, DOI https://doi.org/10.1016/0024-3795%2880%2990168-8
D. C. Smolarski, - G. W. Stewart,
*Simultaneous iteration for computing invariant subspaces of non-Hermitian matrices*, Numer. Math.**25**(1975/76), no. 2, 123–136. MR**400677**, DOI https://doi.org/10.1007/BF01462265
G. W. Stewart, - J. H. Wilkinson,
*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422** *Handbook for automatic computation. Vol. II*, Springer-Verlag, New York-Heidelberg, 1971. Linear algebra; Compiled by J. H. Wilkinson and C. Reinsch; Die Grundlehren der Mathematischen Wissenschaften, Band 186. MR**0461856**- H. E. Wrigley,
*Accelerating the Jacobi method for solving simultaneous equations by Chebyshev extrapolation when the eigenvalues of the iteration matrix are complex*, Comput. J.**6**(1963/64), 169–176. MR**152115**, DOI https://doi.org/10.1093/comjnl/6.2.169

*Further Results on Polynomials Having Least Maximum Modulus Over an Ellipse in the Complex Plane*, Technical Report AEEW-7348, UKAEA, 1963.

*Numerical Study of Dynamic Stability of Macroeconomical Models-Software for MODULECO*, Dissertation, Technical Report INPG-University of Grenoble, 1980. (French) E. H. Dowell, "Nonlinear oscillations of a fluttering plate. II,"

*AIAA J.*, v. 5, 1967, pp. 1856-1862. H. C. Elman,

*Iterative Methods for Large Sparse Nonsymmetric Systems of Linear Equations*, Ph.D. thesis, Technical Report 229, Yale University, 1982. H. C. Elman, Y. Saad & P.Saylor,

*A New Hybrid Chebyshev Algorithm for Solving Nonsymmetric Systems of Linear Equations*. Technical Report, Yale University, 1984.

*Sparse Matrices and Their Uses*(I. S. Duff, ed.), Academic Press, New York, 1981, pp. 109-138.

*Numerical Hopf Bifurcation*, Ph.D. thesis, California Institute of Technology, 1982.

*Queueing Systems*, Vol. 2:

*Computer Applications*, Wiley, New York, London, 1976.

*An Iterative Method for Solving Nonsymmetric Linear Systems with Dynamic Estimation of Parameters*, Ph.D. dissertation. Technical Report UIUCDCS-75-758, University of Illinois at Urbana-Champaign, 1975.

*Lanczos Versus Subspace Iteration for the Solution of Eigenvalue Problems*, Technical Report UCB/SESM-81/04, Dept. of Civil Engineering, Univ. of California at Berkeley, 1980.

*A Look Ahead Lanczos Algorithm for Unsymmetric Matrices*, Technical Report PAM-43, Center for Pure and Applied Mathematics, 1981.

*Rational Krylov Sequence Methods for Eigenvalue Computations*, Technical Report Uminf-97.82, University of Umea, 1982. H. Rutishauser, "Computational aspects of F. L. Bauer’s simultaneous iteration method,"

*Numer. Math.*, v. 13, 1969, pp. 4-13. Y. Saad, "Projection methods for solving Large sparse eigenvalue problems," in

*Matrix Pencils, Proceedings*(Pitea Havsbad, B. Kagstrom and A. Ruhe, eds.), Lecture Notes in Math., vol. 973, Springer-Verlag, Berlin, 1982, pp. 121-144. Y. Saad,

*Least Squares Polynomials in the Complex Plane with Applications to Solving Sparse Nonsymmetric Matrix Problems*, Technical Report RR-276, Dept. of Computer Science, Yale University, 1983.

*Internal. J. Numer. Methods Engrg.*, v. 7, 1973, pp. 379-394.

*Optimum Semi-Iterative Methods for the Solution of Any Linear Algebraic System with a Square Matrix*, Ph.D. Thesis, Technical Report UIUCDCS-R-81-1077, University of Illinois at Urbana-Champaign, 1981. D. C. Smolarski & P. E. Saylor,

*Optimum Parameters for the Solution of Linear Equations by Richardson Iteration*, 1982. Unpublished Manuscript.

*SRRIT-A FORTRAN Subroutine to Calculate the Dominant Invariant Subspaces of a Real Matrix*, Technical Report TR-514, Univ. of Maryland, 1978. D. Taylor,

*Analysis of the Look-Ahead Lanczos Algorithm*, Ph.D. thesis, Technical Report, Univ. of California, Berkeley, 1983.

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

Retrieve articles in all journals with MSC: 65F15, 65F50

Additional Information

Article copyright:
© Copyright 1984
American Mathematical Society