2020/11/16 by Chao Chen, Chen, Chao, Tianyu Liang +3 · 1 citation
Computer Science · Engineering · Materials Science · #2D Materials and Applications #FOS: Computer and information sciences #FOS: Mathematics #Ferroelectric and Negative Capacitance Devices #Mathematical Software (cs.MS) #Numerical Analysis (math.NA) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2011.07769
openalex publication_date 2020/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a randomized algorithm, namely RCHOL, to construct an approximate Cholesky factorization for a given Laplacian matrix (a.k.a., graph Laplacian). From a graph perspective, the exact Cholesky factorization introduces a clique in the underlying graph after eliminating a row/column. By randomization, RCHOL only retains a sparse subset of the edges in the clique using a random sampling developed by Spielman and Kyng. We prove RCHOL is breakdown-free and apply it to solving large sparse linear systems with symmetric diagonally dominant matrices. In addition, we parallelize RCHOL based on the nested dissection ordering for shared-memory machines. We report numerical experiments that demonstrate the robustness and the scalability of RCHOL. For example, our parallel code scaled up to 64 threads on a single node for solving the 3D Poisson equation, discretized with the 7-point stencil on a 1024× 1024 × 1024 grid, a problem that has one billion unknowns.