Solving Finite Element Linear Systems by a Multilevel Incomplete Factorization Algorithm

Abstract

The approximation of partial differential equations by the finite element method results in a large sparse linear system whose condition number ncreases when the mesh is refined (in a way that depends on the differential operator). On the one hand robust methods are required to face engineering applications and multifrontal direct methods satisfy this requirement. On the other hand fast algorithms are desired, multigrid methods being the optimal choice. Multilevel incomplete factorization methods [1-3] exploit the relation between multigrid and gaussian elimination algorithms resulting in a compromise between robustness and low complexity. This compromise depends on the selection of the parameters that control the dropping of elements during the factorization process. In this work we describe the implementation of these methods for general unstructured finite element discretizations. The main ingredients of the algorithm (factorization, multivel generation and dropping strategies) are presented. We also present numerical experiments showing that the implemented algorithm achieves linear complexity for the Poisson problem. Current limitations and possible genralizations are also discussed.