Name
Abstract | ||
|---|---|---|
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 [private communication, 2020]. 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 three-dimensional Poisson equation, discretized with the 7-point stencil on a 1024 x 1024 x 1024 grid, a problem that has one billion unknowns. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1137/20M1380624 | SIAM JOURNAL ON SCIENTIFIC COMPUTING |
Keywords | DocType | Volume |
randomized numerical linear algebra, incomplete Cholesky factorization, sparse matrix, symmetric diagonally dominant matrix, graph Laplacian, random sampling | Journal | 43 |
Issue | ISSN | Citations |
6 | 1064-8275 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chao Chen | 1 | 2032 | 185.26 |
| Tianyu Liang | 2 | 0 | 0.34 |
| George Biros | 3 | 938 | 77.86 |