Scalable Parallel Algorithms for Sparse Linear Systems

V. Kumar and G. Karypis

University of Minnesota

Large sparse linear systems occur in many scientific and engineering applications encountered in military and civilian domains. Such systems are typically solved using either iterative or direct methods. Although highly parallel formulations of dense matrix factorization are well known, it had been a challenge to implement efficient sparse linear system solvers using direct methods, even on moderately parallel computers. This talk will present our recent work on a highly parallel sparse Cholesky factorization algorithm that substantially improves the state of the art in parallel direct solution of sparse linear systems---both in terms of scalability and overall performance. Experiments have shown that this algorithm can easily speedup Cholesky factorization by a factor of at least a few hundred up to 1024 processors, and achieve levels of performance that were unheard of and unimaginable for this problem until very recently.

Fast and accurate graph partitioning algorithms are needed for direct as well iterative parallel sparse solvers. This talk will also present our work on new a multilevel graph partitioning scheme that consistently outperforms the spectral partitioning schemes (which is considered the state-of-the-art) in terms of both cut size and run time. We also used our graph partitioning scheme to compute fill reducing orderings for sparse matrices. Surprisingly, our scheme substantially outperforms the multiple minimum degree algorithm (MMD), which is the most commonly used method for computing fill reducing orderings of a sparse matrix.

  • Click here for a postscript paper mlevel_serial.

  • Click here for a postscript paper mlevel_kway.

  • Click here for a postscript paper mlevel_analysis.

  • Click here for a postscript paper mlevel_parallel.

  • Click here for a postscript paper sparse-cholesky.