Why approximate LU decompositions of finite element discretizations of elliptic operators can be computed with almost linear complexity

Mario Bebendorf

Contact the author: Please use for correspondence this email.
Submission date: 24. Jan. 2005
Pages: 25
published in: SIAM journal on numerical analysis, 45 (2007) 4, p. 1472-1494 
DOI number (of the published article): 10.1137/060669747
Bibtex
with the following different title: Why finite element discretizations can be factored by triangular hierarchical matrices
MSC-Numbers: 35C20, 65F05, 65F50
Keywords and phrases: approximate $lu$ decomposition, non-smooth coefficients, hierarchical matrices
Download full preprint: PDF (481 kB), PS ziped (581 kB)

Abstract:
Although the asymptotic complexity of direct methods for the solution of large sparse finite element systems arising from second-order elliptic partial differential operators is far from being optimal, these methods are often preferred over modern iterative methods. This is mainly due to their robustness. In this article it is shown that an (approximate) LU decomposition exists and that it can be computed in the algebra of hierarchical matrices with almost linear complexity and with the same robustness as the classical LU decomposition.