7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.