|
A geometric theory for preconditioned inverse iteration applied to a subspace
Author(s):
Klaus
Neymeyr.
Journal:
Math. Comp.
71
(2002),
197-216.
MSC (2000):
Primary 65N30, 65N25;
Secondary 65F10, 65F15
Posted:
September 17, 2001
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
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:
-
- 1.
- J.H. Bramble, J.E. Pasciak, and A.V. Knyazev. A subspace preconditioning algorithm for eigenvector/eigenvalue computation. Adv. Comput. Math., 6:159-189, 1996. MR 98c:65057
- 2.
- F. Chatelin. Eigenvalues of matrices. Wiley, Chichester, 1993. MR 94d:65002
- 3.
- E.R. Davidson. The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices. J. Comput. Phys., 17:87-94, 1975. MR 52:2168
- 4.
- E.G. D'yakonov. Iteration methods in eigenvalue problems. Math. Notes, 34:945-953, 1983. MR 86d:65048
- 5.
- E.G. D'yakonov. Optimization in solving elliptic problems. CRC Press, Boca Raton, Florida, 1996. MR 97e:65004
- 6.
- E.G. D'yakonov and A.V. Knyazev. Group iterative method for finding lower-order eigenvalues. Moscow Univ. Comput. Math. Cybern., 2:32-40, 1982. MR 84a:65030
- 7.
- E.G. D'yakonov and A.V. Knyazev. On an iterative method for finding lower eigenvalues. Russian J. Numer. Anal. Math. Modelling, 7(6):473-486, 1992. MR 94f:65035
- 8.
- E.G. D'yakonov and M.Y. Orekhov. Minimization of the computational labor in determining the first eigenvalues of differential operators. Math. Notes, 27:382-391, 1980. MR 82a:65086
- 9.
- S.K. Godunov, V.V. Ogneva, and G.P. Prokopov. On the convergence of the modified method of steepest descent in the calculation of eigenvalues. Amer. Math. Soc. Transl. Ser. 2, 105:111-116, 1976. MR 48:3235
- 10.
- G.H. Golub and C.F. Van Loan. Matrix Computations. John Hopkins University Press, Baltimore, MD, 3rd edition, 1996. MR 97g:65006
- 11.
- 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.
- 12.
- I. Ipsen. Computing an eigenvector with inverse iteration. SIAM Rev., 39:254-291, 1997. MR 98f:65041
- 13.
- A.V. Knyazev. Preconditioned eigensolvers--an oxymoron? Electron. Trans. Numer. Anal., 7:104-123, 1998. MR 99h:65068
- 14.
- K. Neymeyr. A posteriori error estimation for elliptic eigenproblems. Sonderforschungsbereich 382, Universität Tübingen, Report 132, 1999.
- 15.
- K. Neymeyr. A geometric theory for preconditioned inverse iteration. I: Extrema of the Rayleigh quotient. Linear Algebra Appl. 322(1-3):61-85, 2001. CMP 2001:06
- 16.
- K. Neymeyr. A geometric theory for preconditioned inverse iteration. II: Convergence estimates. Linear Algebra Appl. 322(1-3):87-104, 2001. CMP 2001:06
- 17.
- B.N. Parlett. The symmetric eigenvalue problem. Prentice Hall, Englewood Cliffs New Jersey, 1980. MR 81j:65063
- 18.
- W.V. Petryshyn. On the eigenvalue problem
 with unbounded and non-symmetric operators  and  . Philos. Trans. Roy. Soc. Math. Phys. Sci., 262:413-458, 1968. MR 36:5747 - 19.
- B.A. Samokish. The steepest descent method for an eigenvalue problem with semi-bounded operators. Izv. Vyssh. Uchebn. Zaved. Mat., 5:105-114, 1958.
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(2000):
65N30, 65N25,
65F10, 65F15
Retrieve articles in all Journals with MSC
(2000):
65N30, 65N25,
65F10, 65F15
Additional Information:
Klaus
Neymeyr
Affiliation:
Mathematisches Institut der Universität Tübingen, Auf der Morgenstelle 10, 72076 Tübingen, Germany
Email:
neymeyr@na.uni-tuebingen.de
DOI:
10.1090/S0025-5718-01-01357-6
PII:
S 0025-5718(01)01357-6
Keywords:
Symmetric eigenvalue problem,
subspace iteration,
preconditioning,
multigrid,
inverse iteration
Received by editor(s):
July 27, 1999.
Posted:
September 17, 2001
Copyright of article:
Copyright
2001,
American Mathematical Society
|
Comments: webmaster@ams.org