I am curious how to quickly compute the eigenvalues for arbitrary matrices, sparse or dense, restricted on some given interval of interest.
Suppose we have an arbitrary $n\times n$ matrix $A$, normally the complexity of the computing all the eigenvalues for $A$ is $O(n^3)$, I wonder if we could find an algorithm that does the same job while only bears an $O(n^2)$ or less complexity, or more specifically, the eigenvalues on an interval $(a,b)$. Is this possible at all?
For symmetric matrix, to my knowledge, we could use bisection method to somewhat get the job done, I would like to know if there are other tricks for general matrices as well.