<div class="gmail_quote">On Fri, May 20, 2011 at 14:55, Thomas Witkowski <span dir="ltr"><<a href="mailto:thomas.witkowski@tu-dresden.de">thomas.witkowski@tu-dresden.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
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?</blockquote>
</div><br><div>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.</div>
<div><br></div><div>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.</div>