# Implementation of a $O(n \log(n))$ method to compute eigenvalues of real symmetric tridiagonal matrices

I just came upon this paper, which details the implementation of a fast method to get eigenvalues of tridiagonal symmetric matrices :

Coakley, Ed S.; Rokhlin, Vladimir, A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices

This method relies on a divide and conquer algorithm, and enables the computation of eigenvalues in $$O(n \log(n))$$ complexity, while traditional methods, such as the ones in LAPACK have a $$O(n^2)$$ complexity.

I am quite surprised this has not become a reference. The detail of the algorithm is provided into the paper, but look quite tedious. Do you know if this method has already been implemented in a package or third-party library?

Though the paper is correct to point out the importance of solving the tridiagonal-symmetric eigenproblem in the course of solving the general-symmetric eigenproblem, it neglects to mention that the "frontend" procedure between these two scenarios (Householder tridiagonalization) already requires $$\mathcal O(n^3)$$ flops. This will dominate the overall complexity of the general-symmetric problem, no matter how you solve the inner tridiagonal problem.