Fast Sparse Matrix Permutation for Mesh-Based Direct Solvers
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908802023948288 |
|---|---|
| author | Zarebavami, Behrooz Mahmoud, Ahmed H. Dodik, Ana Yuan, Changcheng Porumbescu, Serban D. Owens, John D. Dehnavi, Maryam Mehri Solomon, Justin |
| author_facet | Zarebavami, Behrooz Mahmoud, Ahmed H. Dodik, Ana Yuan, Changcheng Porumbescu, Serban D. Owens, John D. Dehnavi, Maryam Mehri Solomon, Justin |
| contents | We present a fast sparse matrix permutation algorithm tailored to linear systems arising from triangle meshes. Our approach produces nested-dissection-style permutations while significantly reducing permutation runtime overhead. Rather than enforcing strict balance and separator optimality, the algorithm deliberately relaxes these design decisions to favor fast partitioning and efficient elimination-tree construction. Our method decomposes permutation into patch-level local orderings and a compact quotient-graph ordering of separators, preserving the essential structure required by sparse Cholesky factorization while avoiding its most expensive components. We integrate our algorithm into vendor-maintained sparse Cholesky solvers on both CPUs and GPUs. Across a range of graphics applications, including single factorizations, repeated factorizations, our method reduces permutation time and improves the sparse Cholesky solve performance by up to 6.27x. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_00898 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fast Sparse Matrix Permutation for Mesh-Based Direct Solvers Zarebavami, Behrooz Mahmoud, Ahmed H. Dodik, Ana Yuan, Changcheng Porumbescu, Serban D. Owens, John D. Dehnavi, Maryam Mehri Solomon, Justin Graphics Distributed, Parallel, and Cluster Computing We present a fast sparse matrix permutation algorithm tailored to linear systems arising from triangle meshes. Our approach produces nested-dissection-style permutations while significantly reducing permutation runtime overhead. Rather than enforcing strict balance and separator optimality, the algorithm deliberately relaxes these design decisions to favor fast partitioning and efficient elimination-tree construction. Our method decomposes permutation into patch-level local orderings and a compact quotient-graph ordering of separators, preserving the essential structure required by sparse Cholesky factorization while avoiding its most expensive components. We integrate our algorithm into vendor-maintained sparse Cholesky solvers on both CPUs and GPUs. Across a range of graphics applications, including single factorizations, repeated factorizations, our method reduces permutation time and improves the sparse Cholesky solve performance by up to 6.27x. |
| title | Fast Sparse Matrix Permutation for Mesh-Based Direct Solvers |
| topic | Graphics Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2602.00898 |