# Preprint No. MPIMD/11-01

#### Author(s): Peter Benner, Thomas Mach

#### Email: thomas.mach@googlemail.com

#### Date: 2011-02-11

#### Abstract:

The preconditioned inverse iteration [Ney01] is an efficient
method to compute the smallest eigenpair of a symmetric positive definite
matrix ℋ. Here we use this method to find the smallest eigenvalues of a
hierarchical matrix [Hac99]. The storage complexity of the data-sparse
ℋ-matrices is almost linear. We use ℋ-arithmetic to precondition with
an approximate inverse of M or an approximate Cholesky decomposition of
M. In general ℋ-arithmetic is of linear-polylogarithmic complexity, so the
computation of one eigenvalue is cheap.
We extend the ideas to the computation of inner eigenvalues by computing an
invariant subspaces S of (M-\mu I)² by subspace
preconditioned inverse iteration. The eigenvalues of the generalized matrix
Rayleigh quotient \mu_{M}(S) are the wanted inner eigenvalues of M. The
idea of using (M-\mu I)² instead of M is known as folded
spectrum method [WanZ94].
Numerical results substantiate the convergence properties and show that the
computation of the eigenvalues is superior to existing
algorithms for non-sparse matrices.

#### BibTeX:

@TECHREPORT{MPIMD11-01,

author = {Peter Benner and Thomas Mach},

title = {The Preconditioned Inverse Iteration for Hierarchical Matrices},

number = {MPIMD/11-01},

month = feb,

year = 2011,

institution = {Max Planck Institute Magdeburg},

type = {Preprint},

note = {Available from \url{http://www.mpi-magdeburg.mpg.de/preprints/}},

}