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

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?)

  • [1] W. E. Arnoldi, "The principle of minimized iteration in the solution of the matrix eigenvalue problem," Quart Appl. Math., v. 9, 1951, pp. 17-29. MR 0042792 (13:163e)
  • [2] F. L. Bauer, "Das Verfahren der Treppeniteration und Verwandte Verfahren zur Losung Algebraischer Eigenwertprobleme," Z. Angew. Math. Phys., v. 8, 1957, pp. 214-235. MR 0088049 (19:461b)
  • [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] M Clint & A. Jennings, "The evaluation of eigenvalues and eigenvectors of real symmetric matrices by simultaneous iteration method," J. Inst. Math. Appl., v. 8, 1971, pp. 111-121. MR 0297116 (45:6174)
  • [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] K. K. Gupta, "Eigensolution of damped structual systems," Internat. J. Numer. Methods Engrg., v. 8, 1974, pp. 877-911. MR 0488842 (58:8347a)
  • [10] K. K. Gupta, "On a numerical solution of the supersonic panel flutter eigenproblem," Internat. J. Numer. Methods Engrg., v. 10, 1976, pp. 637-645. MR 0488844 (58:8347c)
  • [11] A. L. Hageman & D. M. Young, Applied Iterative Methods, Academic Press, New York, 1981. MR 630192 (83c:65064)
  • [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 & W. J. Stewart, "Simultaneous iteration for partial eigensolution of real matrices," J. Math. Inst. Appl., v. 15, 1980, pp. 351-361. MR 0408221 (53:11986)
  • [14] A. Jennings & W. J. Stewart, "A simultaneous iteration algorithm for real matrices," ACM Trans. Math. Software, v. 7, 1981, pp. 184-198. MR 618513 (83d:65118)
  • [15] A. Jepson, Numerical Hopf Bifurcation, Ph.D. thesis, California Institute of Technology, 1982.
  • [16] S. Karlin, Mathematical Methods and Theory in Games, Programming, and Economics, Vol. I, Addison-Wesley, Reading, Mass., 1959. MR 1160778 (93a:90001)
  • [17] L. Kaufman, Matrix Methods of Queueing Problems, Technical Report TM-82-11274-1, Bell Laboratories, 1982. MR 723109 (84k:60127)
  • [18] L. Kleinrock, Queueing Systems, Vol. 2: Computer Applications, Wiley, New York, London, 1976.
  • [19] 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. 255-282. MR 0042791 (13:163d)
  • [20] A. J. Laub, Schur Techniques in Invariant Imbedding Methods for Solving Two Point Boundary Value Problems, 1982. (To appear.) MR 837458
  • [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] T. A. Manteuffel, "The Tchebychev iteration for nonsymmetric linear systems," Numer. Math., v. 28, 1977, pp. 307-327. MR 0474739 (57:14373)
  • [23] T. A. Manteuffel, "Adaptive procedure for estimation of parameter for the nonsymmetric Tchebychev iteration," Numer. Math., v. 28, 1978, pp. 187-208. MR 509674 (80d:65047)
  • [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] B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, N. J., 1980. MR 570116 (81j:65063)
  • [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] T. J. Rivlin, The Chebyshev Polynomials, Wiley, New York, 1976. MR 0450850 (56:9142)
  • [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., v. 34, 1980, pp. 269-295. MR 591435 (81m:65055)
  • [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., v. 41, 1971, pp. 68-80. MR 0272257 (42:7138)
  • [35] E. Seneta, "Computing the stationary distribution for infinite Markov chains," in Large Scale Matrix Problems (A. Björck, R. J. Plemmons & H. Schneider, eds.), Elsevier, North-Holland, New York, 1981, pp. 259-267. MR 591434 (82a:60103)
  • [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., v. 25, 1976, pp. 123-136. MR 0400677 (53:4508)
  • [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 (32:1894)
  • [42] J. H. Wilkinson & C. Reinsch, Handbook for Automatic Computation, Vol. II, Linear Algebra, Springer-Verlag, New York, 1971. MR 0461856 (57:1840)
  • [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., v. 6, 1963, pp. 169-176. MR 0152115 (27:2095)

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

American Mathematical Society