Implicitly restarted Arnoldi with purification for the shift-invert transformation
HTML articles powered by AMS MathViewer
- by Karl Meerbergen and Alastair Spence PDF
- Math. Comp. 66 (1997), 667-689 Request permission
Abstract:
The need to determine a few eigenvalues of a large sparse generalised eigenvalue problem $Ax=\lambda Bx$ with positive semidefinite $B$ arises in many physical situations, for example, in a stability analysis of the discretised Navier-Stokes equation. A common technique is to apply Arnoldi’s method to the shift-invert transformation, but this can suffer from numerical instabilities as is illustrated by a numerical example. In this paper, a new method that avoids instabilities is presented which is based on applying the implicitly restarted Arnoldi method with the $B$ semi-inner product and a purification step. The paper contains a rounding error analysis and ends with brief comments on some extensions.References
- Ȧke Björck, Solving linear least squares problems by Gram-Schmidt orthogonalization, Nordisk Tidskr. Informationsbehandling (BIT) 7 (1967), 1–21. MR 214275, DOI 10.1007/bf01934122
- K. A. Cliffe, T. J. Garratt, and A. Spence, Eigenvalues of the discretized Navier-Stokes equation with application to the detection of Hopf bifurcations, Adv. Comput. Math. 1 (1993), no. 3-4, 337–356. MR 1242379, DOI 10.1007/BF02072015
- K. A. Cliffe, T. J. Garratt, and A. Spence, Eigenvalues of block matrices arising from problems in fluid mechanics, SIAM J. Matrix Anal. Appl. 15 (1994), no. 4, 1310–1318. MR 1293919, DOI 10.1137/S0895479892233230
- J. W. Daniel, W. B. Gragg, L. Kaufman, and G. W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt $QR$ factorization, Math. Comp. 30 (1976), no. 136, 772–795. MR 431641, DOI 10.1090/S0025-5718-1976-0431641-8
- Thomas Ericsson, A generalised eigenvalue problem and the Lánczos algorithm, Large scale eigenvalue problems (Oberlech, 1985) North-Holland Math. Stud., vol. 127, North-Holland, Amsterdam, 1986, pp. 95–119. MR 875436, DOI 10.1016/S0304-0208(08)72642-2
- Thomas Ericsson and Axel Ruhe, The spectral transformation Lánczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. Comp. 35 (1980), no. 152, 1251–1268. MR 583502, DOI 10.1090/S0025-5718-1980-0583502-2
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
- Roger G. Grimes, John G. Lewis, and Horst D. Simon, A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems, SIAM J. Matrix Anal. Appl. 15 (1994), no. 1, 228–272. MR 1257633, DOI 10.1137/S0895479888151111
- D. S. Malkus, Eigenproblems associated with the discrete LBB condition for incompressible finite elements, Internat. J. Engrg. Sci. 19 (1981), no. 10, 1299–1310. MR 660563, DOI 10.1016/0020-7225(81)90013-6
- Bahram Nour-Omid, Beresford N. Parlett, Thomas Ericsson, and Paul S. Jensen, How to implement the spectral transformation, Math. Comp. 48 (1987), no. 178, 663–673. MR 878698, DOI 10.1090/S0025-5718-1987-0878698-5
- B. Philippe and M. Sadkane, Improving the spectral transformation block Arnoldi method, Second IMACS Symposium on Iterative Methods in Linear Algebra (P.S. Vassilevski and S.D. Margenov, eds.), IMACS Series in Computational and Applied Mathematics, vol. 3, IMACS Symposium on Iterative Methods in Linear Algebra, 1996, pp. 57–63.
- D. S. Scott, The advantages of inverted operators in Rayleigh-Ritz approximations, SIAM J. Sci. Statist. Comput. 3 (1982), no. 1, 68–75. MR 651868, DOI 10.1137/0903006
- D. C. Sorensen, Implicit application of polynomial filters in a $k$-step Arnoldi method, SIAM J. Matrix Anal. Appl. 13 (1992), no. 1, 357–385. MR 1146670, DOI 10.1137/0613025
- Homer F. Walker, Implementation of the GMRES method using Householder transformations, SIAM J. Sci. Statist. Comput. 9 (1988), no. 1, 152–163. MR 922869, DOI 10.1137/0909010
Additional Information
- Karl Meerbergen
- Affiliation: LMS Numerical Technologies, Interleuvenlaan 70, 3001 Heverlee, Belgium
- Email: km@lmsnit.be
- Alastair Spence
- Affiliation: School of Mathematical Sciences, University of Bath, Claverton Down, Bath BA2 7AY, United Kingdom
- Email: A.Spence@maths.bath.ac.uk
- Received by editor(s): May 9, 1995
- Received by editor(s) in revised form: November 5, 1995
- © Copyright 1997 American Mathematical Society
- Journal: Math. Comp. 66 (1997), 667-689
- MSC (1991): Primary 65F15, 65F50
- DOI: https://doi.org/10.1090/S0025-5718-97-00844-2
- MathSciNet review: 1408376