A new algorithm for the symmetric tridiagonal eigenvalue problem (Q1311389)

The authors propose and analyse a new method for the computation of some or all of the eigenvalues of a real symmetric band matrix. The method, which uses previous ideas of the first author [Comput. Math. Appl. 14, 591-622 (1987; Zbl 0634.65036)], can approximate within \(\varepsilon\) to all the eigenvalues of a real symmetric tridiagonal matrix \(A\) using at most \[ n^ 2([3\log_ 2 (625 n^ 6)]+ (83n- 34) [\log_ 2 (\log_ 2 ((\lambda_ 1- \lambda_ 2)/ (2\varepsilon))/ \log_ 2 (25n))]) \] arithmetic operations, where \(\lambda_ 1\) and \(\lambda_ 2\) are the extremal eigenvalues of \(A\).