Premium
The preconditioned inverse iteration for hierarchical matrices
Author(s) -
Benner Peter,
Mach Thomas
Publication year - 2013
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.1830
Subject(s) - mathematics , cholesky decomposition , eigenvalues and eigenvectors , rayleigh quotient iteration , inverse , inverse iteration , power iteration , eigendecomposition of a matrix , rayleigh quotient , invariant subspace , krylov subspace , matrix (chemical analysis) , computation , iterative method , algorithm , pure mathematics , linear subspace , physics , geometry , materials science , quantum mechanics , composite material
SUMMARY The preconditioned inverse iteration is an efficient method to compute the smallest eigenpair of a symmetric positive definite matrix M . Here we use this method to find the smallest eigenvalues of a hierarchical matrix. The storage complexity of the data‐sparse H ‐matrices is almost linear. We use H ‐arithmetic to precondition with an approximate inverse of M or an approximate Cholesky decomposition of M . In general, H ‐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 subspace S of ( M − μI ) 2 by subspace preconditioned inverse iteration. The eigenvalues of the generalized matrix Rayleigh quotient μ M ( S ) are the desired inner eigenvalues of M . The idea of using ( M − μI ) 2 instead of M is known as the folded spectrum method. As we rely on the positive definiteness of the shifted matrix, we cannot simply apply shifted inverse iteration therefor. Numerical results substantiate the convergence properties and show that the computation of the eigenvalues is superior to existing algorithms for non‐sparse matrices.Copyright © 2012 John Wiley & Sons, Ltd.