Algorithm 1xxx: ParU: a parallel task-based sparse multifrontal unsymmetric LU factorization

ParU is a sparse direct solver based on a novel parallel multifrontal algorithm. In contrast with UMFPACK, which draws its performance from highly customized data structures and parallel BLAS libraries, the goal of ParU is to maximize the sources of parallelism it can exploit through OpenMP tasking and nested parallelism, i.e., node -level parallelism within its rectangular frontal matrices, and tree -level parallelism across the assembly tree. ParU relies on the analysis phase of UMFPACK, with the addition of strategies to exploit tree parallelism. The factorization phase is based on a variant of the multifrontal method, where the fronts are unsymmetric and rectangular shaped. Similarly to UMFPACK, it exploits sparse pivots within the fronts, but simplifies the data structures to allow for coarser-grained node parallelism (mostly through large GEMM (matrix multiplication) and TRSM (triangular solve)). Experimental results show that ParU is competitive in terms of performance with state-of-the-art libraries as UMFPACK, SuperLU, and MUMPS.