Parallel GPU-Accelerated Randomized Construction of Approximate Cholesky Preconditioners
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915312341876736 |
|---|---|
| author | Liang, Tianyu Chen, Chao Yaniv, Yotam Luo, Hengrui Tench, David Li, Xiaoye S. Buluc, Aydin Demmel, James |
| author_facet | Liang, Tianyu Chen, Chao Yaniv, Yotam Luo, Hengrui Tench, David Li, Xiaoye S. Buluc, Aydin Demmel, James |
| contents | We introduce a parallel algorithm to construct a preconditioner for solving a large, sparse linear system where the coefficient matrix is a Laplacian matrix (a.k.a., graph Laplacian). Such a linear system arises from applications such as discretization of a partial differential equation, spectral graph partitioning, and learning problems on graphs. The preconditioner belongs to the family of incomplete factorizations and is purely algebraic. Unlike traditional incomplete factorizations, the new method employs randomization to determine whether or not to keep fill-ins, i.e., newly generated nonzero elements during Gaussian elimination. Since the sparsity pattern of the randomized factorization is unknown, computing such a factorization in parallel is extremely challenging, especially on many-core architectures such as GPUs. Our parallel algorithm dynamically computes the dependency among row/column indices of the Laplacian matrix to be factorized and processes the independent indices in parallel. Furthermore, unlike previous approaches, our method requires little pre-processing time. We implemented the parallel algorithm for multi-core CPUs and GPUs, and we compare their performance to other state-of-the-art methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02977 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parallel GPU-Accelerated Randomized Construction of Approximate Cholesky Preconditioners Liang, Tianyu Chen, Chao Yaniv, Yotam Luo, Hengrui Tench, David Li, Xiaoye S. Buluc, Aydin Demmel, James Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Numerical Analysis We introduce a parallel algorithm to construct a preconditioner for solving a large, sparse linear system where the coefficient matrix is a Laplacian matrix (a.k.a., graph Laplacian). Such a linear system arises from applications such as discretization of a partial differential equation, spectral graph partitioning, and learning problems on graphs. The preconditioner belongs to the family of incomplete factorizations and is purely algebraic. Unlike traditional incomplete factorizations, the new method employs randomization to determine whether or not to keep fill-ins, i.e., newly generated nonzero elements during Gaussian elimination. Since the sparsity pattern of the randomized factorization is unknown, computing such a factorization in parallel is extremely challenging, especially on many-core architectures such as GPUs. Our parallel algorithm dynamically computes the dependency among row/column indices of the Laplacian matrix to be factorized and processes the independent indices in parallel. Furthermore, unlike previous approaches, our method requires little pre-processing time. We implemented the parallel algorithm for multi-core CPUs and GPUs, and we compare their performance to other state-of-the-art methods. |
| title | Parallel GPU-Accelerated Randomized Construction of Approximate Cholesky Preconditioners |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Numerical Analysis |
| url | https://arxiv.org/abs/2505.02977 |