Wide Quotient Trees for Finite Element Problems

Abstract

In solving the system of linear equations $Ax = b$ where $A$ is an $n \times n$ large sparse symmetric positive definite matrix, one important objective is to minimize fill. One approach is to partition the matrix so that its corresponding quotient graph is a tree and then use block factorization techniques to solve the system. We examine several methods for generating valid quotient tree partitionings of grid graphs and find that those producing short wide quotient trees are superior for large enough graphs. We then give an algorithm for generating wide quotient tree partitionings of a more general class of graphs. Bounds on its storage and computational requirements are provided and compared to those of a generalized nested dissection algorithm.