|
Abstract : |
Abstract. Computing a fill-reducing ordering of a sparse matrix is a central problem in the solution of sparse linear systems using direct methods. In recent years, there has been significant research in developing a sparse direct solver suitable for message-passing multiprocessors. However, computing the ordering step in parallel remains a challenge and there are very few methods available. This paper describes a new scheme called parallel contracted ordering which is a combination of a new parallel nested dissection heuristic and any serial ordering method. The new nested dissection heuristic called Shrink-Split ND (SSND) is based on parallel graph contraction. For a system with N unknowns, the complexity of SSND is O(, |
