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?

  • 2
    $\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$ 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
  • $\begingroup$ 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. $\endgroup$ Oct 10 '19 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.