# Preprint No. MPIMD/10-01

#### Author(s): Peter Benner, Thomas Mach

#### Email: thomas.mach@googlemail.com

#### Date: 2010-11-17

#### Abstract:

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.

#### BibTeX:

@TECHREPORT{MPIMD10-01,

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{http://www.mpi-magdeburg.mpg.de/preprints/}},

}