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
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.


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. 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 0088049, 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 0297116
  • [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 0488842, https://doi.org/10.1002/nme.1620090216
  • [10] K. K. Gupta, Author’s reply to a recent discussion: “A further 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), 509–518)” (Internat. J. Numer. Methods Engrg. 10 (1976), no. 2, 474–475), by L. Meirovitch, Internat. J. Numer. Methods Engrg. 10 (1976), no. 4, 974. MR 0488844, https://doi.org/10.1002/nme.1620100426
  • [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 0408221
  • [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 0474739, 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 0272257, 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 0400677, 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/1964), 169–176. MR 0152115, https://doi.org/10.1093/comjnl/6.2.169

Similar Articles

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

American Mathematical Society