Fast Sparse Matrix Permutation for Mesh-Based Direct Solvers
This paper targets a very specific bottleneck in graphics and simulation pipelines: the permutation step before sparse Cholesky factorization. Instead of spending a lot of time chasing perfectly balanced separators, the authors use patch-level local orderings plus a compact quotient-graph ordering for separators. The result is a nested-dissection-style layout that preserves the structure solvers need, but is cheaper to build.
For developers, the practical win is less time lost before the actual solve starts, especially in workflows with repeated factorizations. The authors report up to 6.27x improvement in sparse Cholesky solve performance across graphics applications, and they’ve integrated the method into vendor-maintained CPU and GPU solvers. The paper was submitted Jan. 31, 2026, revised June 4, 2026, and is slated for SIGGRAPH 2026 conference proceedings.
“reduces permutation time and improves the sparse Cholesky solve performance by up to 6.27x”
- what
- A fast sparse matrix permutation algorithm for triangle-mesh linear systems
- who
- Authors include Behrooz Zarebavami, Ahmed H. Mahmoud, Ana Dodik, Changcheng Yuan, Serban D. Porumbescu, John D. Owens, Maryam Mehri Dehnavi, and Justin Solomon
- when
- Submitted Jan. 31, 2026; revised June 4, 2026; appearing in SIGGRAPH 2026 proceedings
- impact
- Reported to reduce permutation time and improve sparse Cholesky solve performance by up to 6.27x
Meaningful speedups for a common solver bottleneck
Follow graphics updates
See relevant stories in your personalized news feed.
Discussion