We present a method that in certain sense stores the inverse of the stiffness matrix in $O(NlogN)$ memory places, where $N$ is the number of degrees of freedom and hence the matrix size. The setup of this storage format requires $O\left(N^{3/2}\right)$ arithmetic operations. However, once the setup is done, the multiplication of the inverse matrix and a vector can be performed with $O(NlogN)$ operations. This approach applies to the first order finite element discretization of linear elliptic and parabolic problems in triangular domains, but it can be generalized to higher-order elements, variety of problems, and general domains. The method is based on a special hierarchical enumeration of vertices and on a hierarchical elimination of suitable degrees of freedom. Therefore, we call it hierarchical condensation of degrees of freedom.

EUDML-ID : urn:eudml:doc:287849
Mots clés:
Mots clés:

@article{702950,
     title = {A direct solver for finite element matrices requiring $O(N \log N)$ memory places},
     booktitle = {Applications of Mathematics 2013},
     series = {GDML\_Books},
     publisher = {Institute of Mathematics AS CR},
     address = {Prague},
     year = {2013},
     pages = {225-239},
     mrnumber = {MR3204447},
     zbl = {1340.65038},
     url = {http://dml.mathdoc.fr/item/702950}
}

Vejchodský, Tomáš. A direct solver for finite element matrices requiring $O(N \log N)$ memory places, dans Applications of Mathematics 2013, GDML_Books,  (2013), pp. 225-239. http://gdmltest.u-ga.fr/item/702950/