13

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?

Anton Menshov
  • 8,672
  • 7
  • 38
  • 94
Sai Venkat
  • 241
  • 1
  • 4
  • 2
    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 05 '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 05 '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 06 '17 at 09: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 06 '17 at 09:58
  • I wrote this paper on SVD of Loewner matrices, https://www.researchgate.net/publication/295857431_Fast_Singular-Value_Decomposition_of_Loewner_Matrices_for_State-space_Macromodeling. The idea is applicable to any matrix with low displacement rank, such as Toeplitz and Hankel. – Amit Hochman Oct 10 '19 at 06:49

0 Answers0