# A direct solver for finite element matrices requiring $O\left(NlogN\right)$ memory places

• Applications of Mathematics 2013, Publisher: Institute of Mathematics AS CR(Prague), page 225-239

top

## Abstract

top
We present a method that in certain sense stores the inverse of the stiffness matrix in $O\left(NlogN\right)$ 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\left(NlogN\right)$ 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.

## How to cite

top

Vejchodský, Tomáš. "A direct solver for finite element matrices requiring $O(N \log N)$ memory places." Applications of Mathematics 2013. Prague: Institute of Mathematics AS CR, 2013. 225-239. <http://eudml.org/doc/287849>.

@inProceedings{Vejchodský2013,
abstract = {We present a method that in certain sense stores the inverse of the stiffness matrix in $O(N\log N)$ memory places, where $N$ is the number of degrees of freedom and hence the matrix size. The setup of this storage format requires $O(N^\{3/2\})$ arithmetic operations. However, once the setup is done, the multiplication of the inverse matrix and a vector can be performed with $O(N\log N)$ 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.},
author = {Vejchodský, Tomáš},
booktitle = {Applications of Mathematics 2013},
keywords = {sparse direct solver; hierarchical condensation; finite element method; sparse matrices; algorithm},
location = {Prague},
pages = {225-239},
publisher = {Institute of Mathematics AS CR},
title = {A direct solver for finite element matrices requiring $O(N \log N)$ memory places},
url = {http://eudml.org/doc/287849},
year = {2013},
}

TY - CLSWK
AU - Vejchodský, Tomáš
TI - A direct solver for finite element matrices requiring $O(N \log N)$ memory places
T2 - Applications of Mathematics 2013
PY - 2013
CY - Prague
PB - Institute of Mathematics AS CR
SP - 225
EP - 239
AB - We present a method that in certain sense stores the inverse of the stiffness matrix in $O(N\log N)$ memory places, where $N$ is the number of degrees of freedom and hence the matrix size. The setup of this storage format requires $O(N^{3/2})$ arithmetic operations. However, once the setup is done, the multiplication of the inverse matrix and a vector can be performed with $O(N\log N)$ 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.
KW - sparse direct solver; hierarchical condensation; finite element method; sparse matrices; algorithm
UR - http://eudml.org/doc/287849
ER -

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.