language: en

An Asymptotically Optimal Minimum Degree Ordering of Regular Grids

B. Kumar, P. Sadayappan, C.-H. Huang
Department of Computer and Information Science The Ohio State University,
Columbus, OH 43210

Abstract It has previously been shown that there exists a minimum degree ordering for regular grids that is considerably worse than nested dissection in terms of fill-in and operations for factorization [1]. This paper proves the existence of a minimum degree ordering for regular grids that has the same optimal asymptotic order complexity for fill-in and operation count as nested dissection. The analysis is verified by showing exact match between analytical prediction and experimental measurement. The analysis motivates a peripheral preordering strategy for use with the popular multiple minimum degree (MMD) algorithm, and is shown to consistently reduce fill-in and operation count for regular grids.

Keywords: Sparse Matrices, Finite Element Grids, Minimum Degree Ordering, Computational Complexity. AMS(MOS) subject classifications: 65F05, 65F50, 68R10

1 Introduction