A Nondeterministic Parallel Algorithm for General Unsymmetric Sparse LU Factorization

Abstract

A parallel algorithm for the direct LU factorization of general unsymmetric sparse matrices is presented. The algorithm D2 is based on a new nondeterministic parallel pivot search that finds a compatible pivot set${\bf S}$ of size m, followed by a parallel rank-m update. These two steps alternate until switching to dense matrix code or until the matrix is factored. The algorithm is based on a shared-memory multiple-instruction-multiple-data (MIMD) model and takes advantage of both concurrency and (gather-scatter) vectorization. The detection of parallelism due to sparsity is based on Markowitz’s strategy, an unsymmetric ordering method. As a result, D2 finds more potential parallelism for matrices with highly asymmetric nonzero patterns than algorithms that construct an elimination tree using a symmetric ordering method (minimum degree or nested dissection, for example) applied to the symmetric pattern of ${\bf A} + {\bf A}^{\bf T} $ or ${\bf A}^{\bf T} {\bf A}$. The pivot search exploits more parallelism than previous algorithms that are based on unsymmetric ordering methods. Possible extensions to the D2 algorithm are discussed, including the use of dense matrix kernels and a software-combining tree to enhance parallelism in the pivot search.