Summary

PDE models are a mainstay of computational science and engineering, but even linear elliptic PDEs are hard to solve in 3D. Standard direct methods based on sparse Gaussian elimination scale terribly for three-dimensional problems, taking $O(N^2)$ time and $O(N^{4/3})$ memory for relatively large $N$. Preconditioned iterative methods are often an attractive alternative, but these methods can be finicky: they depend on many tuning parameters, and for hard problems they require expert care and feeding.

The goal of this project is to combine sparse factorization methods and fast solvers for rank-structured matrices to build fast, cache-aware algorithms and robust solvers for general linear PDE discretizations. Our approach is based on the idea that correctly-ordered factorization of PDE discretization matrices yields factors that are not only largely sparse, but that even dense blocks formed during factorization have low rank structure. This low rank structure reflects the interpretation of these intermediate matrices as discretizations of boundary integral equations. By using both sparsity and low rank structure, our methods dramatically improve the scalability of direct methods, yet remain robust without the parameter tuning required for typical iterative methods.

Links

Papers

J. Chadwick and D. Bindel, “An Efficient Solver for Sparse Linear Systems Based on Rank-Structured Cholesky Factorization,” Jul. 2015.
@techreport{2015-rsc,
  author = {Chadwick, Jeffrey and Bindel, David},
  title = {An Efficient Solver for Sparse Linear Systems Based on
             Rank-Structured {Cholesky} Factorization},
  month = jul,
  year = {2015},
  arxiv = {1507.05593},
  link = {http://arxiv.org/pdf/1507.05593},
  code = {https://github.com/jeffchadwick/rank_structured_cholesky},
  status = {unrefereed}
}

Abstract:

Direct factorization methods for the solution of large, sparse linear systems that arise from PDE discretizations are robust, but typically show poor time and memory scalability for large systems. In this paper, we describe an efficient sparse, rank-structured Cholesky algorithm for solution of the positive definite linear system Ax=b when A comes from a discretized partial-differential equation. Our approach combines the efficient memory access patterns of conventional supernodal Cholesky algorithms with the memory efficiency of rank-structured direct solvers. For several test problems arising from PDE discretizations, our method takes less memory than standard sparse Cholesky solvers and less wall-clock time than standard preconditioned iterations.

Talks

An Efficient Solver for Sparse Linear Systems based on Rank-Structured Cholesky Factorization

TSIMF Workshop on Structured Matrix Computations with Applications
rscmeeting external invited

An Efficient Solver for Sparse Linear Systems based on Rank-Structured Cholesky Factorization

Workshop on Forty Years of Nested Dissection, University of Waterloo
rscmeeting external