Accelerating Sparse Factorization Methods with Algorithmic and Hardware Advances

Many extreme-scale simulation codes encompass multiphysics components in multiple spatial and length scales. The resulting discretized sparse linear systems can be highly indefinite, nonsymmetric and extremely ill-conditioned. For such problems, factorization based algorithms are often the most robust algorithmic choices among many alternatives. We present our recent research on novel parallel factorization algorithms that are efficient for solving such problems. From algorithm side, we incorporate data-sparse low-rank structures, such as hierarchical matrix algebra, to achieve lower arithmetic and communication complexity as well as robust preconditioner. From parallelization side, we exploit sparse data structures represented by DAGs and trees to schedule coarse-grained tasks and SIMD/SIMT for fine-grained parallelism. We will illustrate both theoretical and practical aspects of the methods, and demonstrate their performance on manycore architectures including GPU clusters and the latest Intel Xeon Phi KNL platforms, using a variety of real world problems.