Implicitly restarted Arnoldi with purification for the shift-invert transformation

Meerbergen, Karl; Spence, Alastair

doi:10.1090/S0025-5718-97-00844-2

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