Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems

Author: Youcef Saad
Journal: Math. Comp. 42 (1984), 567-588
MSC: Primary 65F15; Secondary 65F50
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.

References [Enhancements On Off] (What's this?)

  • 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
  • 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
  • A. Clayton, Further Results on Polynomials Having Least Maximum Modulus Over an Ellipse in the Complex Plane, Technical Report AEEW-7348, UKAEA, 1963.
  • 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, 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.
  • 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
  • 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
  • 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 Sparse Matrices and Their Uses (I. S. Duff, ed.), Academic Press, New York, 1981, pp. 109-138.
  • 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
  • A. Jepson, Numerical Hopf Bifurcation, Ph.D. thesis, California Institute of Technology, 1982.
  • 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
  • L. Kleinrock, Queueing Systems, Vol. 2: Computer Applications, Wiley, New York, London, 1976.
  • 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
  • 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.
  • Thomas A. Manteuffel, The Tchebychev iteration for nonsymmetric linear systems, Numer. Math. 28 (1977), no. 3, 307–327. MR 474739, DOI
  • 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
  • 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.
  • 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, A Look Ahead Lanczos Algorithm for Unsymmetric Matrices, Technical Report PAM-43, Center for Pure and Applied Mathematics, 1981.
  • Theodore J. Rivlin, The Chebyshev polynomials, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR 0450850
  • A. Ruhe, 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.
  • Y. Saad, Variations on Arnoldi’s method for computing eigenelements of large unsymmetric matrices, Linear Algebra Appl. 34 (1980), 269–295. MR 591435, DOI
  • G. Sander, C. Bon & M. Geradin, "Finite element analysis of supersonic panel flutter," Internal. J. Numer. Methods Engrg., v. 7, 1973, pp. 379-394.
  • D. H. Sattinger, Bifurcation of periodic solutions of the Navier-Stokes equations, Arch. Rational Mech. Anal. 41 (1971), 66–80. MR 272257, DOI
  • E. Seneta, Computing the stationary distribution for infinite Markov chains, Linear Algebra Appl. 34 (1980), 259–267. MR 591434, DOI
  • 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. D. C. Smolarski & P. E. Saylor, Optimum Parameters for the Solution of Linear Equations by Richardson Iteration, 1982. Unpublished Manuscript.
  • 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
  • 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. D. Taylor, Analysis of the Look-Ahead Lanczos Algorithm, Ph.D. thesis, Technical Report, Univ. of California, Berkeley, 1983.
  • 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

Similar Articles

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