Standard multigrid and domain decomposition methods do not work, but I have large 3D problems and direct solvers are not an option. What methods should I try?

How are my choices affected by the following considerations?

  • coefficients vary over several orders of magnitude, or
  • finite element versus finite different methods are used
  • 1
    $\begingroup$ In 3D, iterative solvers normally perform poorly, I recommend referring to some HSS-matrix reordering direct solver from Ming Gu, Xia, and Chandrasekaran. $\endgroup$ – Shuhao Cao Dec 18 '11 at 20:50

EDIT: The previous comment is now completely outdated. Please see the related work section of the published paper for a more complete discussion, and Elemental, Clique, and PSP for the underlying software. Two-grid preconditioners are also worth investigating.

  • $\begingroup$ Is there any update to this? $\endgroup$ – Aron Ahmadia Apr 3 '12 at 10:36

I think in general it's worth remembering that the most efficient methods we have (geometric and algebraic multigrid as well as, to a degree, domain decomposition) rely on the fact that solutions of PDEs are often smooth and that solving a coarser problem may yield a good approximation for the fine scale problem. The problem with the Helmholtz equation for high frequencies is that this assumption is not true: you do need a relatively fine mesh to represent the solution, and coarse mesh solvers will not be able to produce anything that's of much use. Consequently, the typical approaches to good preconditioners don't work in that case, and that is the underlying reason why there are no real good options in your case short of just throwing lots of processors at the problem; whether you use finite elements or finite difference then obviously doesn't make much of a difference since the problem is at the continuous level.


The H-matrix stuff from Jack Poulson and Lexing Ying is the most efficient method I know. This should be released in the spring but they have given presentations on it.

  • 2
    $\begingroup$ I should probably qualify your statement by saying that we have solved large-scale high-frequency problems with a moving PML approach efficiently on thousands of cores for very high frequency, but we have not yet tested the H-matrix strategy at that scale. The reasoning is that it does not have as much theoretical justification in 3d, despite the fact that it will be more scalable from a parallel computing perspective. $\endgroup$ – Jack Poulson Nov 30 '11 at 19:02

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.