Ordering Techniques for Singly Bordered Block Diagonal Forms for Unsymmetric Parallel Sparse Direct Solvers

摘要

The solution of large sparse linear systems of equations is one of the cornerstones of scientific computation. In many applications is is important to be able to solve these systems as rapidly as possible. One approach for very large problems is to reorder the system matrix to bordered block diagonal form and then to solve the block system in parallel. In this paper, we consider the problem of efficiently ordering unsymmetric systems to singly bordered block diagonal form. Algorithms such as the MONET algorithm of Hu, Maguire and Blake (2000) that depend upon computing a representation of AA(sup T) can be prohibitively expensive when a single ( or small number of) matrix factorizations are required. We therefore work with the graph of A(sup T) + A or B + B (sup T, where B is a row permutation of A) and propose new reordering algorithms that use only vertex separators and wide separators of this graph. Numerical experiments demonstrate that our methods are efficient and can produce bordered forms that are competitive with those obtained using MONET.