Why Finite Element Discretizations Can Be Factored by Triangular Hierarchical Matrices
Author:
- Mario BebendorfMBMario Bebendorf
- 1 January 2007
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Numerical Analysis
- Vol. 45 (4) , 1472-1494
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 which can be computed in the algebra of hierarchical matrices with almost linear complexity and with the same robustness as the classical $LU$ decomposition. Low-precision approximations may be used for preconditioning iterative solvers. As a byproduct we prove that Schur complements of stiffness matrices can be approximated with almost linear complexity.
Keywords
This publication has 27 references indexed in Scilit:
- Hierarchical LU Decomposition-based Preconditioners for BEMComputing, 2004
- Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficientsMathematics of Computation, 2004
- Construction and Arithmetics of H -MatricesComputing, 2003
- Adaptive Low-Rank Approximation of Collocation MatricesComputing, 2003
- Semi On-Line Scheduling on Two Identical MachinesComputing, 1999
- NETGEN An advancing front 2D/3D-mesh generator based on abstract rulesComputing and Visualization in Science, 1997
- Stability of block LU factorizationNumerical Linear Algebra with Applications, 1995
- A Fast Direct Algorithm for the Solution of the Laplace Equation on Regions with Fractal BoundariesJournal of Computational Physics, 1994
- On the fast matrix multiplication in the boundary element method by panel clusteringNumerische Mathematik, 1989
- Rapid solution of integral equations of classical potential theoryJournal of Computational Physics, 1985