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.
- Slicing the spectrum
- Symmetric hierarchical matrices
ASJC Scopus subject areas
- Applied Mathematics
- Computational Mathematics