6

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...

Anton Menshov
  • 8,672
  • 7
  • 38
  • 94
lorniper
  • 593
  • 4
  • 13

2 Answers2

3

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.

3

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

that also has a follow-up

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).

Anton Menshov
  • 8,672
  • 7
  • 38
  • 94