# Fast Eigenvalue and SVD Solver for Structured Matrices

I am looking for a fast Eigenvalue and SVD solver for small dense structured matrices (Hankel and Toeplitz). I have searched for efficient implementations in libraries like MKL but I am not able to find anything specific to structured matrices. I found a set of interesting papers on the subject:

Luk and Qiao, "A Fast Eigenvalue algorithm for Hankel matrices" which uses Lancoz tridiagonalization based on FFT and a QR like diagonalization of the tridiagonal matrix for computing eigenvalues with a complexity of $O(n^2\log(n))$.

Luk and Qiao, "A fast symmetric SVD algorithm for square Hankel matrices"

Do any of the libraries out there or any implementation you know of use this as I would like to reuse as much as possible? Are there any algorithms which achieve bounds better than this for structured matrices?

• A cursory Google search yielded these two Matlab packages written by Sanzheng Qiao (from McMaster U): (1) - for general (rectangular) matrices and (2) - for symmetric matrices. Is this more or less what you were looking for? – GoHokies May 5 '17 at 16:54
• Are you looking to compute all singular values / eigenvalues, or just a few of them? Is the matrix low-rank / does it have clustered eigenvalues? – Richard Zhang May 5 '17 at 21:25
• @GoHokies, Thanks for the links. I am not necessarily looking for the implementation of those methods by Qiao. More of a papers/library research on faster than $\mathcal O(N^3)$ SVD for Hankel\Toeplitz matrices. – Anton Menshov May 6 '17 at 9:55
• @RichardZhang, for my purposes, the matrices are mostly low-rank, so I search for the algorithms revealing the first $k$ singular-values (+singular vectors) with controlled tolerance $\epsilon$ ($\sigma_k/\sigma_1<\epsilon$). – Anton Menshov May 6 '17 at 9:58
• I wrote this paper on SVD of Loewner matrices, researchgate.net/publication/…. The idea is applicable to any matrix with low displacement rank, such as Toeplitz and Hankel. – Amit Hochman Oct 10 '19 at 6:49