A Stable Non-deterministic Parallel Algorithm for General Unsymmetric Sparse LU Factorization

Résumé du livre

Abstract: "We present a parallel algorithm for the direct LU factorization of general unsymmetric sparse matrices. The algorithm, D2, is based on a new nondeterministic parallel pivot search that finds a compatible pivot set 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 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