Randomized Cholesky Factorization in Parallel
ACM Student Research Competition: Graduate Poster
ACM Student Research Competition: Undergraduate Poster
TimeWednesday, 18 November 20208:30am - 5pm EDT
DescriptionLarge sparse SDD (symmetric diagonally dominant) linear systems arise from solving elliptic PDEs and graph problems. Exact Cholesky factorization leads to excessive fill-in, especially in 3D. Our approach is to subsample the (dense) Schur complement update and construct an (approximate) sparse preconditioner. To optimize for practical performance, we reorder the original matrix to exploit the sparsity pattern. In particular, we apply a log(P)-level nested dissection followed by AMD (approximate minimum degree) ordering at the leaf level, where P is the number of threads. This ordering naturally leads to a parallel method. Results show that our preconditioner outperformed standard incomplete Cholesky preconditioner with much less iterations and scaled up to 64 threads on a multicore CPU. Our poster has three major parts: the randomized sampling algorithm, the parallel algorithm/implementation, and results on parallel scalability as well as comparison to incomplete Cholesky.