![]() |
| Das Dokument ist frei verfügbar |
|
| | Nachweis | Kein Nachweis verfügbar |
|
| 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. |
|
|