Preprint No. MPIMD/10-01

Title: Computing all or some Eigenvalues of symmetric ℋ-Matrices

Author(s): Peter Benner, Thomas Mach


Date: 2010-11-17


We use a bisection method, [Par80, p. 51], to compute the eigenvalues of a symmetric Hl-matrix M. The number of negative eigenvalues of M−μI is computed via the LDLT factorisation of M − μI. For dense matrices, the LDLT factorisation is too expensive to yield an efficient eigenvalue algorithm in general, but not for Hl-matrices. In the special structure of Hl-matrices there is an LDLT factorisation with linear-polylogarithmic complexity. 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. For all n eigenvalues, O(n^2 (log n)^4 log (||M||_2/eps_ev)) flops are needed to compute all eigenvalues with an accuracy eps_ev. It is also possible to compute only eigenvalues in a specific interval or the j-th smallest one. Numerical experiments demonstrate the efficiency of the algorithm, in particular for the case where some interior eigenvalues are required.


author = {Peter Benner and Thomas Mach},
title = {Computing all or some Eigenvalues of symmetric ℋ-Matrices},
number = {MPIMD/10-01},
month = nov,
year = 2010,
institution = {Max Planck Institute Magdeburg},
type = {Preprint},
note = {Available from \url{}},

Published in: SIAM J. on Sci. Computing, DOI: 10.1137/100815323

Download MPIMD/10-01