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

Question

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?

Answer 1

I think the method has too much implementation complexity and too narrow applicability to be worth it.

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.

Similar difficulties exist in the context of Lanczos algorithms for large sparse/structured eigenproblems. Although they project down to tridiagonal systems, these instances are much smaller in size than the original sparse system. So solving tridiagonal eigenproblems still doesn't drive the overall cost, compared to the cost of the "full-size" matvecs and vector operations incurred by the Lanczos iterations themselves.

The tridiagonal eigenproblem just doesn't occur very often by itself, instead it's typically preceded by other (more expensive) preprocessing. So it would seem that fast algorithms are probably not worth the effort here.