Randomized Cholesky Factorization in Parallel

Student: Tianyu Liang (University of Texas)
Supervisor: Chao Chen (University of Texas)

Abstract: Large 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.

ACM-SRC Semi-Finalist: no

Poster: PDF
Poster Summary: PDF


Back to Poster Archive Listing