A Note on Nested Dissection for Rectangular Grids

Abstract

A new ordering scheme is presented for sparse matrices associated with rectangular grid problems. The new scheme combines features of both the nested dissection and natural orderings to obtain orderings superior to either of these methods for such problems. Asymptotic bounds and experimental results on sparse factorization operations are provided to demonstrate the advantages of the new ordering.