Skip to content
Preprint

Accelerating Direct Sparse Solvers with Graph Computing Accelerators

Nov 2026 · 0 citations · 47 references
Computer Science

Abstract

Solving large sparse linear systems by Gaussian elimination is a challenging computational task due to the introduction of non-zero elements, or fill-in. Practitioners use heuristics such as the nested dissection reordering algorithm to try to reduce fill-in. In practice, reordering codes do not achieve the same parallel scaling as factorization, nor can they exploit AVX instructions or GPUs. Thus, reordering can be the primary runtime bottleneck in large-scale computer-aided engineering applications. We consider the use of a novel accelerator, the UpDown system, to accelerate the METIS multilevel nested dissection reordering algorithm. The UpDown system is designed for a broad class of graph computing and irregular algorithms. We report results for small-scale UpDown systems that will be available commercially in 2027, using validated simulation and FPGA emulation platforms. Our findings indicate that small UpDown systems can speed up METIS by two-orders of magnitude versus a single CPU. Compared to ParMETIS on hundreds of MPI ranks, we anticipate the same small UpDown systems offer speedups of 4 - 7, providing the potential to significantly speed finite element simulations

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.