Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems
HTML articles powered by AMS MathViewer
- by Youcef Saad PDF
- Math. Comp. 42 (1984), 567-588 Request permission
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
- 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 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 10.1007/BF01600502 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 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 10.1002/nme.1620090216
- Louis A. Hageman and David M. Young, Applied iterative methods, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1981. 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 10.1145/355945.355948 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 10.1137/0904037 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 10.1007/BFb0006827 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 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 10.1007/BF01397475 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 Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. 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, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. 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 10.1016/0024-3795(80)90169-X 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 10.1007/BF00250178
- E. Seneta, Computing the stationary distribution for infinite Markov chains, Linear Algebra Appl. 34 (1980), 259–267. MR 591434, DOI 10.1016/0024-3795(80)90168-8 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 10.1007/BF01462265 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, Die Grundlehren der mathematischen Wissenschaften, Band 186, Springer-Verlag, New York-Heidelberg, 1971. Linear algebra; Compiled by J. H. Wilkinson and C. Reinsch. 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 10.1093/comjnl/6.2.169
Additional Information
- © Copyright 1984 American Mathematical Society
- 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