Abstract
The Rational Krylov algorithm for the nonsymmetric matrix pencil eigenvalue problem is described. It is a generalization of the shifted and inverted Lanczos (or Araoldi) 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.
Rational Krylov is the natural alternative when factorization of the matrix is not much more expensive than solution, as e. g. when a multigrid algorithm is used to solve systems.
In one variant several iterations with different shifts are started on the same starting vector. Such iterations can be performed in parallel, yielding a p degree Krylov vector in one iteration on p processors. An analogy to a method of experimentally verifying stability of aircraft structures is shown.
The algorithm is demonstrated on two applied test problems.
The work was partly supported by the Swedish National Board for Technical Development, STU grant 91-1210.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Abbreviations
- AMS(MOS):
-
subject classifications. 65F15
References
W. Arnoldi, The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9 (1951), pp. 17–29.
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. El Dabaghi eds, Elsevier/North-Holland, pp.415–422,1991.
D. L. Boley and G. H. Golub, The nonsymmetric Lanczos algorithm and controllability, Systems Control Lett., 16 (1991), pp. 97–105.
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.
G. Golub, R. Underwood, and J. Wilkinson, The Lanczos algorithm for the symmetric Ax = λBx problem, Tech. Report STAN-CS-72-270, Computer Science, Stanford University, Stanford, CA, 1972.
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.
M. H. Gutknecht, A completed theory for the unsymmetric Lanczos process and related algorithms, part J, SIMAX, 13 (1992), pp. 594–639.
J. Huitfeldt and A. Ruhe, A new algorithm for numerical path following applied to an example from hydro dynamical flow, SISSC, 11 (1990), pp. 1181 – 1192.
W. Kahan, B. Parlett, and E. Jiang, Residual bounds on approximate eigen-systems of nonnormal matrices, SINUM, 19 (1982), pp. 470 - 484.
C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, National Bureau of Standards, Journal of Research, 45 (1950), pp. 255–282.
R. Meyer-Spasche, Some bifurcation diagrams for Taylor vortex flows, Phys. Fluids, 28 (1985), pp. 1248–1252.
R. Meyer-Spasche and H. B. Keller, Computations of the axisymmetric flow between rotating cylinders, Journ. Comp. Physics, 35 (1980), pp. 100 - 109.
C. Paige, Practical use of the symmetric Lanczos process with reorthogonalization, BIT, 10 (1970), pp. 183–195.
C. Paige, The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices, PhD thesis, London University, London, England, 1971.
B. Parlett, Reduction to tridiagonal form and minimal realizations, SIMAX, 13 (1992), pp. 567–593.
B. Parlett and Y. Saad, Complex shift and invert strategies for real matrices, Lin. Alg. Appl., 88 /89 (1987), pp. 575–595.
B. Parlett and D. Scott, The Lanczos algorithm with selective orthogonalization, Math. Comp., 33 (1979), pp. 217–238.
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.
A. Ruhe, Rational Krylov sequence methods for eigenvalue computation, LAA, 58 (1984), pp. 391–405.
Y. Saad, Variations of Arnoldi’s method for computing eigenelements of large unsymmetric matrices, Lin. Alg. Appl., 34 (1980), pp. 269–295.
H. Wittmeyer, Parameteridentifikation bei Strukturen mit benachbarten Eigenfrequenzen speziell bei Flugschwingungsversuchen, Z. Flugwissenschaft und Weltraumforschung, 6 (1982), pp. 80–90.
L. Wittmeyer-Koch, Comparison of the evaluation of a shake test using either the l1-norm or the l2-norm, Tech. Report LiTH-MAT-R-1990-36, Dept of Math. Univ. Linköping, Sweden, 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag New York, Inc
About this paper
Cite this paper
Ruhe, A. (1994). Rational Krylov Algorithms for Nonsymmetric Eigenvalue Problems. In: Golub, G., Luskin, M., Greenbaum, A. (eds) Recent Advances in Iterative Methods. The IMA Volumes in Mathematics and its Applications, vol 60. Springer, New York, NY. https://doi.org/10.1007/978-1-4613-9353-5_10
Download citation
DOI: https://doi.org/10.1007/978-1-4613-9353-5_10
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4613-9355-9
Online ISBN: 978-1-4613-9353-5
eBook Packages: Springer Book Archive