PARA'04 State-of-the-Art
in Scientific Computing
June 20-23, 2004 (Home page)
Updated: 20 February 2004

Efficient ordering techniques for bordered block diagonal forms for unsymmetric parallel sparse direct solvers

Yifan Hu
Wolfram Research, UK
and
Jennifer Scott
Rutherford Appleton Laboratory, UK

The solution of large sparse linear systems of equations is one of the cornerstones of scientific computation. In many applications it 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 that depend upon computing a representation of $AA^T$ can be prohibitively expensive when a single (or small number of) matrix factorizations are required. We therefore work with the graph of $A^T + A$ (or $B + B^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 by an algorithm that uses $AA^T$.

Home page