13
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 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, 2017 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, 2017 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, 2017 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, 2017 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$
    – Amit Hochman
    Oct 10, 2019 at 6:49

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.