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

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.*, 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)**

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