The preconditioned inverse iteration for hierarchical matrices / Peter Benner, Thomas Mach

Abstract

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