A geometric theory for preconditioned inverse iteration applied to a subspace
HTML articles powered by AMS MathViewer
- by Klaus Neymeyr;
- Math. Comp. 71 (2002), 197-216
- DOI: https://doi.org/10.1090/S0025-5718-01-01357-6
- Published electronically: September 17, 2001
- PDF | Request permission
Abstract:
The aim of this paper is to provide a convergence analysis for a preconditioned subspace iteration, which is designated to determine a modest number of the smallest eigenvalues and its corresponding invariant subspace of eigenvectors of a large, symmetric positive definite matrix. The algorithm is built upon a subspace implementation of preconditioned inverse iteration, i.e., the well-known inverse iteration procedure, where the associated system of linear equations is solved approximately by using a preconditioner. This step is followed by a Rayleigh–Ritz projection so that preconditioned inverse iteration is always applied to the Ritz vectors of the actual subspace of approximate eigenvectors. The given theory provides sharp convergence estimates for the Ritz values and is mainly built on arguments exploiting the geometry underlying preconditioned inverse iteration.References
- James H. Bramble, Joseph E. Pasciak, and Andrew V. Knyazev, A subspace preconditioning algorithm for eigenvector/eigenvalue computation, Adv. Comput. Math. 6 (1996), no. 2, 159–189 (1997). MR 1431791, DOI 10.1007/BF02127702
- Françoise Chatelin, Eigenvalues of matrices, John Wiley & Sons, Ltd., Chichester, 1993. With exercises by Mario Ahués and the author; Translated from the French and with additional material by Walter Ledermann. MR 1232655
- Ernest R. Davidson, The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices, J. Comput. Phys. 17 (1975), 87–94. MR 381271, DOI 10.1016/0021-9991(75)90065-0
- E. G. D′yakonov, Some iteration methods in eigenvalue problems, Mat. Zametki 34 (1983), no. 6, 897–912 (Russian). MR 731332
- Eugene G. D′yakonov, Optimization in solving elliptic problems, CRC Press, Boca Raton, FL, 1996. Translated from the 1989 Russian original; Translation edited and with a preface by Steve McCormick. MR 1396083
- E. G. D′yakonov and A. V. Knyazev, A group iteration method for finding the lowest eigenvalues, Vestnik Moskov. Univ. Ser. XV Vychisl. Mat. Kibernet. 2 (1982), 29–34, 81 (Russian). MR 663544
- E. G. D′yakonov and A. V. Knyazev, On an iterative method for finding lower eigenvalues, Russian J. Numer. Anal. Math. Modelling 7 (1992), no. 6, 473–486. MR 1202649, DOI 10.1515/rnam.1992.7.6.473
- E. G. D′jakonov and M. Ju. Orehov, Minimization of computational work in finding the first eigenvalues of differential operators, Mat. Zametki 27 (1980), no. 5, 795–812, 831 (Russian). MR 578262
- S. K. Godunov, V. V. Ogneva, and G. P. Prokopov, The convergence of the modified steepest descent method in the computation of eigenvalues, Partial differential equations (Proc. Sympos. dedicated to the 60th birthday of S. L. Sobolev) (Russian), Izdat. “Nauka”, Moscow, 1970, pp. 77–80 (Russian). MR 324886
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
- I. Ipsen. A history of inverse iteration, volume in Helmut Wielandt, Mathematische Werke, Mathematical Works, Vol. 2: Linear Algebra and Analysis, pages 464–472. Walter de Gruyter, Berlin, 1996.
- Ilse C. F. Ipsen, Computing an eigenvector with inverse iteration, SIAM Rev. 39 (1997), no. 2, 254–291. MR 1453320, DOI 10.1137/S0036144596300773
- Andrew V. Knyazev, Preconditioned eigensolvers—an oxymoron?, Electron. Trans. Numer. Anal. 7 (1998), 104–123. Large scale eigenvalue problems (Argonne, IL, 1997). MR 1667642
- K. Neymeyr. A posteriori error estimation for elliptic eigenproblems. Sonderforschungsbereich 382, Universität Tübingen, Report 132, 1999.
- K. Neymeyr. A geometric theory for preconditioned inverse iteration. I: Extrema of the Rayleigh quotient. Linear Algebra Appl. 322(1–3):61–85, 2001.
- K. Neymeyr. A geometric theory for preconditioned inverse iteration. II: Convergence estimates. Linear Algebra Appl. 322(1–3):87–104, 2001.
- Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1980. MR 570116
- W. V. Petryshyn, On the eigenvalue problem $Tu-\lambda Su=0$ with unbounded and nonsymmetric operators $T$ and $S$, Philos. Trans. Roy. Soc. London Ser. A 262 (1967/68), 413–458. MR 222697, DOI 10.1098/rsta.1968.0001
- B.A. Samokish. The steepest descent method for an eigenvalue problem with semi-bounded operators. Izv. Vyssh. Uchebn. Zaved. Mat., 5:105–114, 1958.
Bibliographic Information
- Klaus Neymeyr
- Affiliation: Mathematisches Institut der Universität Tübingen, Auf der Morgenstelle 10, 72076 Tübingen, Germany
- MR Author ID: 672470
- Email: neymeyr@na.uni-tuebingen.de
- Received by editor(s): July 27, 1999
- Published electronically: September 17, 2001
- © Copyright 2001 American Mathematical Society
- Journal: Math. Comp. 71 (2002), 197-216
- MSC (2000): Primary 65N30, 65N25; Secondary 65F10, 65F15
- DOI: https://doi.org/10.1090/S0025-5718-01-01357-6
- MathSciNet review: 1862995