This thesis is on the numerical computation of eigenvalues of symmetric
hierarchical matrices. The numerical algorithms used for this
computation are derivations of the LR Cholesky algorithm, the
preconditioned inverse iteration, and a bisection method based on LDL factorizations.
The investigation of QR decompositions for H-matrices leads to a new QR
decomposition. It has some properties that are superior to the existing
ones, which is shown by experiments using the HQR decompositions to
build a QR (eigenvalue) algorithm for H-matrices does not progress to a
more efficient algorithm than the LR Cholesky algorithm.
The implementation of the LR Cholesky algorithm for hierarchical
matrices together with deflation and shift strategies yields an
algorithm that require O(n) iterations to find all eigenvalues.
Unfortunately, the local ranks of the iterates show a strong growth in
the first steps. These H-fill-ins makes the computation expensive, so
that O(n³) flops and O(n²) storage are required.
Theorem 4.3.1 explains this behavior and shows that the LR Cholesky
algorithm is efficient for the simple structured Hl-matrices.
There is an exact LDLT factorization for Hl-matrices and an approximate
LDLT factorization for H-matrices in linear-polylogarithmic complexity.
This factorizations can be used to compute the inertia of an H-matrix.
With the knowledge of the inertia for arbitrary shifts, one can compute
an eigenvalue by bisectioning. The slicing the spectrum algorithm can
compute all eigenvalues of an Hl-matrix in linear-polylogarithmic
complexity. A single eigenvalue can be computed in O(k²n log^4 n).
Since the LDLT factorization for general H-matrices is only
approximative, the accuracy of the LDLT slicing algorithm is limited.
The local ranks of the LDLT factorization for indefinite matrices are
generally unknown, so that there is no statement on the complexity of
the algorithm besides the numerical results in Table 5.7.
The preconditioned inverse iteration computes the smallest eigenvalue
and the corresponding eigenvector. This method is efficient, since the
number of iterations is independent of the matrix dimension.
If other eigenvalues than the smallest are searched, then preconditioned
inverse iteration can not be simply applied to the shifted matrix,
since positive definiteness is necessary. The squared and shifted matrix
(M-mu I)² is positive definite. Inner eigenvalues can be computed by
the combination of folded spectrum method and PINVIT. Numerical
experiments show that the approximate inversion of (M-mu I)² is more
expensive than the approximate inversion of M, so that the computation
of the inner eigenvalues is more expensive.
We compare the different eigenvalue algorithms. The preconditioned
inverse iteration for hierarchical matrices is better than the LDLT
slicing algorithm for the computation of the smallest eigenvalues,
especially if the inverse is already available. The computation of inner
eigenvalues with the folded spectrum method and preconditioned inverse
iteration is more expensive. The LDLT slicing algorithm is competitive
to H-PINVIT for the computation of inner eigenvalues.
In the case of large, sparse matrices, specially tailored algorithms for
sparse matrices, like the MATLAB function eigs, are more efficient.
If one wants to compute all eigenvalues, then the LDLT slicing algorithm
seems to be better than the LR Cholesky algorithm. If the matrix is
small enough to be handled in dense arithmetic (and is not an
Hl(1)-matrix), then dense eigensolvers, like the LAPACK function dsyev,
are superior.
The H-PINVIT and the LDLT slicing algorithm require only an almost
linear amount of storage. They can handle larger matrices than
eigenvalue algorithms for dense matrices.
For Hl-matrices of local rank 1, the LDLT slicing algorithm and the LR
Cholesky algorithm need almost the same time for the computation of all
eigenvalues. For large matrices, both algorithms are faster than the
dense LAPACK function dsyev.