Authors: Tianyu Liang (University of California, Berkeley); Chao Chen (North Carolina State University); Yotam Yaniv (Lawrence Berkeley National Laboratory (LBNL)); Hengrui Luo (Rice University); David Tench, Xiaoye Li, and Aydın Buluç (Lawrence Berkeley National Laboratory (LBNL)); James Demmel (University of California, Berkeley); and Jie Chen (Amazon Web Services (AWS))
Abstract: Incomplete Cholesky (IC) is a common memory-efficient preconditioner for large graph Laplacian systems, but classical IC can break down on irregular graphs. Approximate Cholesky (AC) addresses this with randomized dropping that is provably breakdown-free. Its stochastic fill-in pattern, however, resists static parallelization, creating a "setup bottleneck." We present ParAC, which parallelizes the AC sampling rule of Gao, Kyng, and Spielman using dynamic dependency tracking and architecture-aware memory management to execute it efficiently on CPUs and GPUs while preserving its numerical updates. Total time-to-solution speedups over deterministic IC reach 57.3× on CPU and 52.2× on GPU. Algebraic multigrid (AMG) generally remains preferable on structured PDE discretizations. On the irregular graph Laplacians tested, ParAC is up to 7.2× faster than AMG on CPUs and 6.0× faster on GPUs. On 200 heterogeneous SDDM systems, ParAC converges on every instance, whereas the AMG solvers fail on 15 and 19, on CPU and GPU, respectively.
Presentation: file