Distributed sparse Gaussian elimination and orthogonal factorization

We consider the solution of a linear system Ax=b on a distributed memory machine when the matrix A has full rank and is large, sparse and nonsymmetric. We use a parallel cartesian nested dissection algorithm to compute a fill-reducing ordering of A, using a compact representation of the column intersection graph. We develop and implement simple algorithms that use the resulting separator tree to estimate the structure of the factor and to distribute data and perform multifrontal numeric computations. When the matrix is nonsymmetric but square, the numeric computations involve Gaussian elimination with row pivoting; when the matrix is overdetermined, row-oriented Householder transforms are applied to compute the triangular factor of an orthogonal factorization. The main contribution is the formulation of a fully parallel, unified approach to solving nonsymmetric sparse systems using either Gaussian elimination or orthogonal factorization and empirical results to demonstrate that the approach is effective both in reducing fill and achieving good parallel performance on an Intel iPSC/860