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.

**[1]**W. E. Arnoldi,*The principle of minimized iteration in the solution of the matrix eigenvalue problem*, Quart. Appl. Math.**9**(1951), 17–29. MR**0042792**, https://doi.org/10.1090/S0033-569X-1951-42792-9**[2]**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**, https://doi.org/10.1007/BF01600502**[3]**A. Clayton,*Further Results on Polynomials Having Least Maximum Modulus Over an Ellipse in the Complex Plane*, Technical Report AEEW-7348, UKAEA, 1963.**[4]**Maurice Clint and Alan Jennings,*A simultaneous iteration method for the unsymmetric eigenvalue problem*, J. Inst. Math. Appl.**8**(1971), 111–121. MR**297116****[5]**F. D'Almeida,*Numerical Study of Dynamic Stability of Macroeconomical Models-Software for MODULECO*, Dissertation, Technical Report INPG-University of Grenoble, 1980. (French)**[6]**E. H. Dowell, "Nonlinear oscillations of a fluttering plate. II,"*AIAA J.*, v. 5, 1967, pp. 1856-1862.**[7]**H. C. Elman,*Iterative Methods for Large Sparse Nonsymmetric Systems of Linear Equations*, Ph.D. thesis, Technical Report 229, Yale University, 1982.**[8]**H. C. Elman, Y. Saad & P.Saylor,*A New Hybrid Chebyshev Algorithm for Solving Nonsymmetric Systems of Linear Equations*. Technical Report, Yale University, 1984.**[9]**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**, https://doi.org/10.1002/nme.1620090216**[10]**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**, https://doi.org/10.1002/nme.1620090216**[11]**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****[12]**A. Jennings, "Eigenvalue methods and the analysis of structural vibration," In*Sparse Matrices and Their Uses*(I. S. Duff, ed.), Academic Press, New York, 1981, pp. 109-138.**[13]**A. Jennings and W. J. Stewart,*Simultaneous iteration for partial eigensolution of real matrices*, J. Inst. Math. Appl.**15**(1975), 351–361. MR**408221****[14]**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**, https://doi.org/10.1145/355945.355948**[15]**A. Jepson,*Numerical Hopf Bifurcation*, Ph.D. thesis, California Institute of Technology, 1982.**[16]**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****[17]**Linda Kaufman,*Matrix methods for queueing problems*, SIAM J. Sci. Statist. Comput.**4**(1983), no. 3, 525–552. MR**723109**, https://doi.org/10.1137/0904037**[18]**L. Kleinrock,*Queueing Systems*, Vol. 2:*Computer Applications*, Wiley, New York, London, 1976.**[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. MR**0042791****[20]**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**, https://doi.org/10.1007/BFb0006827**[21]**T. A. Manteuffel,*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.**[22]**Thomas A. Manteuffel,*The Tchebychev iteration for nonsymmetric linear systems*, Numer. Math.**28**(1977), no. 3, 307–327. MR**474739**, https://doi.org/10.1007/BF01389971**[23]**Thomas A. Manteuffel,*Adaptive procedure for estimating parameters for the nonsymmetric Tchebychev iteration*, Numer. Math.**31**(1978/79), no. 2, 183–208. MR**509674**, https://doi.org/10.1007/BF01397475**[24]**B. Nour-Omid, B. N. Parlett & R. Taylor,*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.**[25]**Beresford N. Parlett,*The symmetric eigenvalue problem*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. Prentice-Hall Series in Computational Mathematics. MR**570116****[26]**B. N. Parlett & D. Taylor,*A Look Ahead Lanczos Algorithm for Unsymmetric Matrices*, Technical Report PAM-43, Center for Pure and Applied Mathematics, 1981.**[27]**Theodore J. Rivlin,*The Chebyshev polynomials*, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR**0450850****[28]**A. Ruhe,*Rational Krylov Sequence Methods for Eigenvalue Computations*, Technical Report Uminf-97.82, University of Umea, 1982.**[29]**H. Rutishauser, "Computational aspects of F. L. Bauer's simultaneous iteration method,"*Numer. Math.*, v. 13, 1969, pp. 4-13.**[30]**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.**[31]**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.**[32]**Y. Saad,*Variations on Arnoldi’s method for computing eigenelements of large unsymmetric matrices*, Linear Algebra Appl.**34**(1980), 269–295. MR**591435**, https://doi.org/10.1016/0024-3795(80)90169-X**[33]**G. Sander, C. Bon & M. Geradin, "Finite element analysis of supersonic panel flutter,"*Internal. J. Numer. Methods Engrg.*, v. 7, 1973, pp. 379-394.**[34]**D. H. Sattinger,*Bifurcation of periodic solutions of the Navier-Stokes equations*, Arch. Rational Mech. Anal.**41**(1971), 66–80. MR**272257**, https://doi.org/10.1007/BF00250178**[35]**E. Seneta,*Computing the stationary distribution for infinite Markov chains*, Linear Algebra Appl.**34**(1980), 259–267. MR**591434**, https://doi.org/10.1016/0024-3795(80)90168-8**[36]**D. C. Smolarski,*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.**[37]**D. C. Smolarski & P. E. Saylor,*Optimum Parameters for the Solution of Linear Equations by Richardson Iteration*, 1982. Unpublished Manuscript.**[38]**G. W. Stewart,*Simultaneous iteration for computing invariant subspaces of non-Hermitian matrices*, Numer. Math.**25**(1975/76), no. 2, 123–136. MR**400677**, https://doi.org/10.1007/BF01462265**[39]**G. W. Stewart,*SRRIT-A FORTRAN Subroutine to Calculate the Dominant Invariant Subspaces of a Real Matrix*, Technical Report TR-514, Univ. of Maryland, 1978.**[40]**D. Taylor,*Analysis of the Look-Ahead Lanczos Algorithm*, Ph.D. thesis, Technical Report, Univ. of California, Berkeley, 1983.**[41]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422****[42]***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****[43]**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**, https://doi.org/10.1093/comjnl/6.2.169

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

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

Additional Information

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

Article copyright:
© Copyright 1984
American Mathematical Society