Algorithms for Matrix Partitioning and the Numerical Solution of Finite Element Systems

Let $Ax = b$ be a sparse positive definite system of equations arising from the use of the finite element method to solve a two dimensional boundary value problem. A common method of solving these matrix problems is to use Cholesky’s method together with an ordering which yields a small bandwidth or profile. This approach is reasonably efficient provided that the associated finite element mesh does not have appendages and/or holes. In this paper algorithms are described for finding orderings and partitionings of sparse finite element matrix problems. These allow the use of computational and storage techniques which lead to substantial improvements over standard solution methods when the associated mesh has appendages and/or holes. The issue of storage and execution time trade-offs naturally arises and is discussed.