Previous |  Up |  Next


Title: A direct solver for finite element matrices requiring $O(N \log N)$ memory places (English)
Author: Vejchodský, Tomáš
Language: English
Journal: Applications of Mathematics 2013
Volume: Proceedings. Prague, May 15-17, 2013
Issue: 2013
Pages: 225-239
Category: math
Summary: 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. (English)
Keyword: sparse direct solver
Keyword: hierarchical condensation
Keyword: finite element method
Keyword: sparse matrices
Keyword: algorithm
MSC: 65F05
MSC: 65F50
MSC: 65N30
idZBL: Zbl 1340.65038
idMR: MR3204447
Date available: 2017-02-14T09:19:47Z
Last updated: 2017-03-20
Stable URL:


Files Size Format View
ApplMath_02-2013-1_29.pdf 273.6Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo