I'm trying to find the largest eigenvalues of very large $N \times N$ matrices ($N = 10^{10}$ and larger). The matrices are not sparse but the multiplication operation is fast.

For now, I'm using methods without explicit matrix storage, from the simple power method to Krylov-Schur (using petsc/slepc in C). But all these methods require to store at least a vector of size $N$.

Is there a diagonalisation algorithm which does not need as much memory?

  • 2
    $\begingroup$ Wouldn't computing just one matrix vector product already require $O(N)$ memory just to look at the answer? Or is it some sort of streaming process where you get parts of the resultant vector piece by piece? $\endgroup$ – Nick Alger Nov 22 '17 at 15:11
  • 4
    $\begingroup$ The fact that you possess a non-sparse A, whose action can be applied quickly, suggests structure to the problem that these black-box methods cannot access (think FFT-like or FMM-like). I think you will have to appeal to that structure if you hope to beat them in space complexity. For instance, the eigenvalues of DFT are known, you don't need numerical diagonalization to find them. Perhaps your structure can also be diagonalized analytically? I am pessimistic - these Krylov/matvec based methods are already pretty lean to do their work in as little as O(N) space .. $\endgroup$ – rchilton1980 Nov 22 '17 at 15:40
  • $\begingroup$ Yes, a full matrix vector multiplication (with a random vector) already require a $O(N)$ memory (to store the result at least). But I can, by example, only consider a subspace of smaller dimension. To be more precise, I can compute quickly any coefficient of the matrix. $\endgroup$ – Jeannette Nov 22 '17 at 15:40
  • 2
    $\begingroup$ .. that said, you are only looking for an output that requires O(1) space, if you only need the eigenvalue and not the eigenvector. So I hesitate to say it's impossible [eg, if your A was the DFT, your problem already solved] See en.wikipedia.org/wiki/…, for example. $\endgroup$ – rchilton1980 Nov 22 '17 at 15:41
  • $\begingroup$ To answer the second comment I cannot compute analytically the eigenvalues in this case (it's the transfer matrix of a non-integrable statistical model). And I'm also on the "impossible" side, but I've been wrong before $\endgroup$ – Jeannette Nov 22 '17 at 15:49

Your Answer

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

Browse other questions tagged or ask your own question.