Preprint No. MPIMD/11-01

Title: The Preconditioned Inverse Iteration for Hierarchical Matrices

Author(s): Peter Benner, Thomas Mach


Date: 2011-02-11


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 \muM(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.


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{}},

Published in: Numer. Lin. Alg. Appl., DOI: 10.1002/nla.1830

Download MPIMD/11-01