1
$\begingroup$

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?

$\endgroup$
  • 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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.