## Abstract

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 language | English |
---|---|

Pages (from-to) | A485-A496 |

Journal | SIAM Journal on Scientific Computing |

Volume | 34 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2012 |

Externally published | Yes |

## Keywords

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

## ASJC Scopus subject areas

- Applied Mathematics
- Computational Mathematics