Lanczos algorithms for Hermitian system with Toeplitz kernel

Question

Basically, I am trying to compute the SVD of a large Hermitian matrix $H$ using Lanczos iteration, while $H$ consists if a Toeplitz kernel $K$, which should be able to help speed up the matrix-vector computations(using FFT) over conventional Lanczos algorithms.

$$ H(i,j) = P_i * K_{ij}(i-j) * P^*_j $$

In summary, I need the largest few eigenvalues and eigenvectors of $H$, and I was wondering which Lanczos algorithms exactly meet this demand? I notice the PROPACK package, but it seems to me it's not designed for this specific case here and the fact that it's written in Fortran...

Answer 1

In this question, regarding fast eigenvalue/SVD solver for structured matrices, it was adviced by @GoHookies to look into the paper:

• W. Xu, S. Qiao, "A fast symmetric SVD algorithm for square Hankel matrices", Lin. Alg. Appl., vol. 428, no. 2–3, pp. 550–563, Jan. 2008

that also has a follow-up

• K. Brown, S. Qiao, and Y. Wei, "A Lanczos bidiagonalization algorithm for Hankel matrices," Lin. Alg. Appl., vol. 430, no. 5–6, pp. 1531–1543, Mar. 2009

Those papers describe techniques (or parts of the required algorithm) to speed-up the calculation of SVD for structured matrices. The application to Hankel matrices naturally extends to the Toeplitz kernel. In general, they use fast FFT-based matrix-vector products for structured matrices applied to Lanczos iterations.

There is also a Matlab package from the same group of authors available online (with some additional explanation and references) that implements their algorithms.

I personally played with this package for my applications, but I am still yet to confirm the benefits and claimed complexity savings (slow side work in progress).

Answer 2

How large are we talking, here? If the problem can fit onto a single node, you can likely just solve it through Hermitian matrix computations and call it a day, see SLEPc for fast implementations of this. Note that SLEPc is written in C but has Fortran and Python wrappers as well.

Addressing your problem more directly: I do not know of any SVD/EVD solvers that will exploit your Toeplitz kernal and matrix structure without modification. That said, it shouldn't be hard to construct something like this yourself. A common method for extracting the largest eigenvalues (singular values) of a matrix is the Arnoldi method, usually implemented using ARPACK. Here, you can simplify modify the matrix-vector multiplication subroutine yourself to exploit the Toeplitz structure through an FFT, as you said.