Computing all or some eigenvalues of symmetric Hl-matrices

Peter Benner, Thomas Mach

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


We use a bisection method [B. Parlett, The Symmetric Eigenvalue Problem, Prentice- Hall, Englewood Cliffs, NJ, 1980, p. 51] to compute the eigenvalues of a symmetric He-matrix M. The number of negative eigenvalues of M - μI is computed via the LDL T factorization of M - μI. For dense matrices, the LDL T factorization is too expensive to yield an efficient eigenvalue algorithm in general, but not so for He-matrices. In the special structure of He-matrices there is an LDL T factorization 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/ ε ev)) flops are needed to compute all eigenvalues with an accuracy ε ev. It is also possible to compute only eigenvalues in a specific interval or the jth smallest one. Numerical experiments demonstrate the efficiency of the algorithm, in particular for the case when some interior eigenvalues are required.

Original languageEnglish
Pages (from-to)A485-A496
JournalSIAM Journal on Scientific Computing
Issue number1
Publication statusPublished - 2012
Externally publishedYes


  • Eigenvalues
  • He-matrices
  • Slicing the spectrum
  • Symmetric hierarchical matrices

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Computing all or some eigenvalues of symmetric Hl-matrices'. Together they form a unique fingerprint.

Cite this