How can I estimate how much memory will be needed to find eigenvalues and eigenvectors of a given large sparse matrix?

I have a real symmetric matrix with roughly $5 \times 10^4$ rows and columns, and an average of $10$ nonzero elements per row. I would like to find the smallest eigenvalue and the corresponding eigenvector, using the built-in Eigensystem function in Mathematica (which treats the matrix as sparse and uses an ARPACK Arnoldi algorithm). Is there a simple way of estimating how much memory this will take?

  • 1
    $\begingroup$ For your problem, Mathematica's Eigensystem function will be using an Arnoldi-type algorithm for eigenvalue computations (most likely the ARPACK package). In addition to storing the matrix itself, the size of the ARPACK workspace is roughly ${\cal O}(n \times (m+2))$ floats (or doubles), where $n$ is the number of rows/columns of your matrix, and $m$ is the size of your Lanczos basis (see the docs for details). Also, you're looking for the smallest eigenvalue so you'll likely want to do shift-invert, which is likely to add to the total (per-step) memory cost. $\endgroup$ – GoHokies Dec 16 '15 at 11:47
  • $\begingroup$ Also, a minor nitpick: you're not actually diagonalizing the matrix, just computing the invariant subspace associated to your $\lambda_{\rm min}$. $\endgroup$ – GoHokies Dec 16 '15 at 11:49
  • $\begingroup$ @GoHokies I've changed the title of the question to make it clearer (hopefully) that I don't need to diagonalize the matrix. $\endgroup$ – Stephen Powell Dec 16 '15 at 12:13
  • $\begingroup$ @GoHokies I've added a link to the implementation notes, which confirm that Mathematica uses ARPACK. $\endgroup$ – Stephen Powell Dec 16 '15 at 12:28
  • 1
    $\begingroup$ thanks. Have a look here as well. If you're looking for a single eigenvalue, you can try working with an $m ~ 5$, so the total ARPACK memory requirement (excluding that of the matrix inversion when doing a shift-invert) is about the same as that of storing the matrix itself (I'm assuming, cf. your OP, that you have about $10$ nonzeros per row, and due to symmetry only half of those are actually stored in memory). $\endgroup$ – GoHokies Dec 16 '15 at 12:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.