The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: Complex shifts for real matrices. (English) Zbl 0810.65032
Summary: [For part II see Linear Algebra Appl. 197-198, 283-295 (1994; Zbl 0810.65031).]
A new algorithm for the computation of eigenvalues of a nonsymmetric matrix pencil is described. It is a generalization of the shifted and inverted Lanczos (or Arnoldi) algorithm, in which several shifts are used in one run. It computes an orthogonal basis and a small Hessenberg pencil. The eigensolution of the Hessenberg pencil gives Ritz approximations to the solution of the original pencil. It is shown how complex shifts can be used to compute a real block Hessenberg pencil to a real matrix pair.
Two applications, one coming from an aircraft stability problem and the other from a hydrodynamic bifurcation, have been tested and results are reported.
A new algorithm for the computation of eigenvalues of a nonsymmetric matrix pencil is described. It is a generalization of the shifted and inverted Lanczos (or Arnoldi) algorithm, in which several shifts are used in one run. It computes an orthogonal basis and a small Hessenberg pencil. The eigensolution of the Hessenberg pencil gives Ritz approximations to the solution of the original pencil. It is shown how complex shifts can be used to compute a real block Hessenberg pencil to a real matrix pair.
Two applications, one coming from an aircraft stability problem and the other from a hydrodynamic bifurcation, have been tested and results are reported.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
Keywords:
rational Krylov algorithm; Lanczos algorithm; Arnoldi algorithm; double shift; inverse iteration; nonsymmetric matrix pencil; small Hessenberg pencil; Ritz approximations; complex shiftsReferences:
| [1] | W. Arnoldi,The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9 (1951), pp. 17–29. · Zbl 0042.12801 |
| [2] | F. Chatelin and S. Godet-Thobie,Stability analysis in aeronautical industries, in Proceedings of the 2nd Symposium on High-Performance Computing Montpellier, France, M. Durand and F. E. Dabaghi, eds., Elsevier/North-Holland, 1991, pp. 415–422. |
| [3] | T. Ericsson and A. Ruhe,The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. Comp., 35 (1980), pp. 1251–1268. · Zbl 0468.65021 |
| [4] | R. G. Grimes, J. G. Lewis, and H. D. Simon,A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems, tech. report, Appl. Math. Stat. RTS div. Boeing Comp. Serv., M/S 7L-21, Seattle WA 98124, USA, 1991. |
| [5] | J. Huitfeldt and A. Ruhe,A new algorithm for numerical path following applied to an example from hydrodynamical flow, SIAM J. Sci. Stat. Comput., 11 (1990), pp. 1181–1192. · Zbl 0724.65051 · doi:10.1137/0911067 |
| [6] | M. T. Jones and M. L. Patrick,LANZ: Software for solving the large sparse symmetric generalized eigenproblem, Tech. Report MCS-P158-0690, Argonne National Lab, Argonne, IL. Also available from netlib., 1990. |
| [7] | R. B. Morgan and D. Scott,Generalizations of Davidson’s method for computing eigenvalues of sparse symmetric matrices, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 817–825. · Zbl 0602.65020 · doi:10.1137/0907054 |
| [8] | B. Parlett and Y. Saad,Complex shift and invert strategies for real matrices, Lin. Alg. Appl., 88/89 (1987), pp. 575–595. · Zbl 0623.65045 · doi:10.1016/0024-3795(87)90126-1 |
| [9] | B. N. Parlett,The Symmetric Eigenvalue Problem, Prentice Hall, 1980. · Zbl 0431.65017 |
| [10] | A. Ruhe,Numerical methods for the solution of large sparse eigenvalue problems, in Sparse Matrix Techniques, Lect Notes Math 572, V. Barker, ed., Springer Berlin-Heidelberg-New York, 1976, pp. 130–184. |
| [11] | A. Ruhe,The two-sided Arnoldi algorithm for nonsymmetric eigenvalue problems, in Matrix Pencils, LNM 973, B. Kågström and A. Ruhe, eds., Springer-Verlag, Berlin Heidelberg New York, 1983, pp. 104–120. · Zbl 0502.65022 |
| [12] | A. Ruhe,Rational Krylov sequence methods for eigenvalue computation, Lin. Alg. Appl., 58 (1984), pp. 391–405. · Zbl 0554.65025 · doi:10.1016/0024-3795(84)90221-0 |
| [13] | A. Ruhe,Rational Krylov algorithms for nonsymmetric eigenvalue problems, in Recent Advances in Iterative Methods, IMA Volumes in Mathematics and its Applications 60, G. Golub, A. Greenbaum, and M. Luskin, eds., Springer-Verlag, New York, 1993, pp. 149–164. · Zbl 0803.65045 |
| [14] | A. Ruhe,Rational Krylov algorithms for nonsymmetric eigenvalue problems, II: Matrix pairs, Lin. Alg. Appl., 197/198, (1994), pp. 283–296. · Zbl 0810.65031 · doi:10.1016/0024-3795(94)90492-8 |
| [15] | Y. Saad,Variations of Arnoldi’s method for computing eigenelements of large unsymmetric matrices, Lin. Alg. Appl., 34 (1980), pp. 269–295. · Zbl 0456.65017 · doi:10.1016/0024-3795(80)90169-X |
| [16] | D. S. Scott,Solving sparse symmetric generalized eigenvalue problems without factorization, SIAM J. Numer. Anal., 18 (1981), pp. 102–110. · Zbl 0478.65023 · doi:10.1137/0718008 |
| [17] | D. C. Sorensen,Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal Appl. 13 (1992), pp. 357–385. · Zbl 0763.65025 · doi:10.1137/0613025 |
| [18] | G. W. Stewart and J. G. Sun,Matrix Perturbation Theory, Academic Press, 1990. · Zbl 0706.65013 |
| [19] | D. B. Szyld,Criteria for combining inverse and Rayleigh quotient iteration, SIAM J. Numer. Anal., 25 (1988), pp. 1369–1375. · Zbl 0665.65031 · doi:10.1137/0725078 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
