An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems

Abstract

A formal definition of a nested dissection ordering of the graph of a general sparse symmetric matrix A is given. After introducing some preliminary results which provide a direct relationship between the structures of A and its triangular factor L, where $A = LL^T $, some results about fill for nested dissection orderings are provided. Finally, a heuristic algorithm is described for finding a nested dissection ordering for an undirected graph, along with appropriate data structures and a storage allocation scheme for a linear equation solver to use such orderings. The ordering algorithm/linear equation solver combination is applied to the graphs of matrices arising in typical finite element applications, and numerical experiments are provided which indicate that our combination of ordering and solution schemes is superior to standard band or envelope schemes as long as the problems are moderately large.