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?

  • 1
    $\begingroup$ 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? $\endgroup$ – GoHokies May 5 '17 at 16:54
  • $\begingroup$ 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? $\endgroup$ – Richard Zhang May 5 '17 at 21:25
  • $\begingroup$ @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. $\endgroup$ – Anton Menshov May 6 '17 at 9:55
  • $\begingroup$ @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$). $\endgroup$ – Anton Menshov May 6 '17 at 9:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.