I've been considering using a multigrid method to calculate the eigenvalues of a particular PDE. I know that multigrid is extremely good at finding the least eigenvalues and their associated eigenvectors, in part because these eigenvectors are very smooth. Is multigrid also a good method to calculate all the eigenvalues and eigenvectors of a PDE?

  • $\begingroup$ Trying a new tag out, as I don't see the point of having separate tags for eigenvalues and eigenvectors. Feel free to undo if you don't like it. $\endgroup$ – J. M. Dec 3 '11 at 5:20
  • $\begingroup$ Sounds good to me. $\endgroup$ – Dan Dec 3 '11 at 13:10

For large problems, you are almost always interested in eigenvalues with specific properties instead of all the eigenvalues at once. Eigenvalue methods for such problems are generally based on solving with a shifted operator. Multigrid can often be used to solve these shifted problems. The SLEPc documentation contains a practical description of many of these algorithms. The library solves the linear systems in the shift-and-invert methods using PETSc, so you can experiment with multigrid (and other) preconditioners when solving eigenvalue problems.

  • $\begingroup$ In this case, I am interested in all of the eigenvalues, or at least a substantial fraction of the lowest eigenvalues. What I'm trying to do is find the eigenvalues and eigenvectors of part of the spatial part of a parabolic PDE, and use those eigenvectors as a basis for solving the whole problem. $\endgroup$ – Dan Dec 1 '11 at 1:47
  • $\begingroup$ The inverse of many differential operators is compact which casues the inverse of the corresponding discretized operator to be well-approximated by a low rank matrix. That is likely the key to your algorithm. SLEPc can find many eigenvalues in a region, but it usually makes sense to find a number that is small compared to the rank of the operator. So you might find a few tens or hundreds, or even a few thousand if necessary, but you likely would hopefully not ask for millions of eigenvalues (even if the discrete model had billions of unknowns). $\endgroup$ – Jed Brown Dec 1 '11 at 2:19
  • $\begingroup$ In that case, is multigrid still a good method for finding hundreds or thousands of eigenvalues? $\endgroup$ – Dan Dec 1 '11 at 3:20
  • 1
    $\begingroup$ That depends on the problem. Note that we are talking about using multigrid as a preconditioner inside the shifted solves in a shift-and-invert or Krylov-Schur algorithm. It's not multigrid finding the eigenvalues any more than a saw builds a house. Compared to direct solves, multigrid has fast setup, but relatively high cost per solution. If the algorithm can use many solves with the same matrix and if you can afford the memory/time to factor the matrix, a direct solver might be better. $\endgroup$ – Jed Brown Dec 1 '11 at 3:51

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.