Implementation of Nested Dissection Method Using Block Elimination
Hashim Saber, Charles Bryan

Abstract
In this paper, we consider the problem of solving an 2 2 n × n sparse positive definite system AU = b , arising from the use of finite difference methods to solve an elliptic boundary value problem on an n × n mesh where = 2 −1 k n where k is a positive integer. The large sparse linear system can be solved directly in an efficient way using nested dissection method, originally proposed by Alan George. This paper demonstrates two algorithms for finding orderings using a version of the nested dissection method which leads to block Gaussian elimination of the matrix A. Implementation of these algorithms is pursued and the issue of storage and execution time tradeoffs is discussed.

Full Text: PDF