We investigate the application of the LR Cholesky algorithm to symmetric hierarchical matrices. The data-sparsity of these matrices make the otherwise expensive LR Cholesky algorithm applicable, as long as the data-sparsity is preserved. We will see that the data-sparsity of hierarchical matrices is not well preserved.
We will explain this behavior by applying a theorem on the structure preservation of diagonal plus semiseparable matrices under LR Cholesky transformations.

The CSC group published 3 new preprints in the last 5 days:

• Peter Benner, Tobias Breiten: On optimality of interpolation-based low-rank approximations of large-scale matrix equations
• Peter Benner, Martin Köhler, Jens Saak: Sparse-Dense Sylvester Equations in ℋ₂-Model Order Reduction
• Thomas Mach, Jens Saak: Towards an ADI iteration for Tensor Structured Equations

The computation of eigenvalues is one of the core topics of numerical mathematics. We will discuss an eigenvalue algorithm for the computation of inner eigenvalues of a large, symmetric, and positive definite matrix M based on the preconditioned inverse iteration x_i+1 = x_i - B^-1 (Mx_i - μ(x_i) x_i), and the folded spectrum method (replace M by (M-σI)²). We assume that M is given in the tensor train matrix format and use the TT-toolbox from I.V. Oseledets (see http://spring.inm.ras.ru/osel/) for the numerical computations. We will present first numerical results and discuss the numerical difficulties.

I give two talks on Computing Inner Eigenvalues of Matrices in Tensor Train Format. The first one on September 06 (ENUMATH 11, Leicester, UK) and the second one on September 22 (GAMM Workshop Applied and Numerical Linear Algebra, Bremen)

On August 23 (15:50) I give a talk at the ILAS 2011 (in Braunschweig) on Why the LR Cholesky algorithm does not work for hierarchical matrices.

On April 19 (16:20) I give a talk at the GAMM 2011 (in Graz) in section S17.2 - Eigenvalue Problems on Preconditioned Inverse Iteration for Hierarchical Matrices.

The preconditioned inverse iteration 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. 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.

We use a bisection method to compute the eigenvalues of a symmetric ℋ_ℓ-matrix M. The bisection method requires only matrix-size independent many iterations to find an eigenvalue up to the desired accuracy, so that an eigenvalue can be found in linear-polylogarithmic time. Numerical experiments demonstrate the efficiency of the algorithm, in particular for the case where some interior eigenvalues are required.

On November 05 I give a talk at the CSC Welcome Colloquium on Hierarchical Matrices: Concepts, Applications and Eigenvalues. In the last section the figure on the left hand side is used.

On September 27 I give a talk at the 23rd Chemnitz FEM Symposium on Preconditioned Inverse Iteration for ℋ-Matrices.