[petsc-users] Direct solver for 3D-FEM

[Jed Brown]

On Fri, May 20, 2011 at 14:55, Thomas Witkowski <
thomas.witkowski at tu-dresden.de> wrote:

> Could one of you explain me why direct solvers (I make use of UMFPACK)
> seems to work quite bad for 3D-FEM? For a small test case, I take a unite
> square/box and refine it globally (bisectioning of triangle/tetrahedrons). I
> solve a six order PDE  (that leads to symmetric but indefinite matrices) on
> it. In 2D the resulting system has 49.923 rows with 808.199 non zeros,
> UMFPACK solves the system within 2.8 seconds. For 3D I've refine the box
> such that the resulting matrix has more or less the same number of non
> zeros, in this case 898.807 on 27.027 rows. UMFPACK needs 32 seconds to
> solve it, so more than 10 time as for the 2D case. Even if I make use of
> fourth order Lagrange functions for the 2D case, which leads to much denser
> matrices (49.923 rows and 2.705.927 non zeros), UMFPACK solves it within 3.2
> seconds. Is there any good reason for it?


It has to do with maximal independent sets, or (more roughly) that the ratio
of surface area/volume (3D) is larger than perimeter/area (2D). This also
affects the amount of communication. You can try using MUMPS instead of
Umfpack, but it won't change the asymptotics.

For PDE problems in 2D, direct solvers with optimal ordering need O(n log n)
memory and O(n^{1.5}) flops. In 3D, they need O(n^{4/3}) memory and O(n^2)
flops.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20110520/74ad7ad9/attachment.htm>