On the Application of the Minimum Degree Algorithm to Finite Element Systems

We describe an efficient implementation of the so-called minimum degree algorithm, which experience has shown to produce efficient orderings for sparse positive definite systems. Our algorithm is a modification of the original, tailored to finite element problems, and is shown to induce a partitioning in a natural way. The partitioning is then refined so as to significantly reduce the number of nonnull off-diagonal blocks. This refinement is important in practical terms because it reduces storage overhead in our linear equation solver, which utilizes the ordering and partitioning produced by our algorithm. Finally, we provide some numerical experiments comparing our ordering/solver package to a more conventional band-oriented package.