A comparison of parallel iterative methods for ILU triangular solves
math.NA, cs.NA
Submitted: 2026-10-31
Updated: 2026-10-31
Code: https://github.com/PFLAREProject/PFLARE
Project page: https://petsc.org
License: http://creativecommons.org/licenses/by/4.0/
The gist: Exact triangular solves parallelise poorly, limited by the size and number of the level sets, so on GPUs the factors from incomplete LU (ILU) factorisations are often solved approximately with…
Abstract
Exact triangular solves parallelise poorly, limited by the size and number of the level sets, so on GPUs the factors from incomplete LU (ILU) factorisations are often solved approximately with parallel iterative methods. We compare four such methods: a Jacobi method, an Incomplete Sparse Approximate Inverse (ISAI), GMRES polynomials, and AIRG, a reduction multigrid built on GMRES polynomials, for which we introduce a parallel coarse/fine splitting that bounds the diagonal dominance ratio of the fine-fine block. We test them with ILU(0) and ILU(1) factors of canonical PDE problems and 91 SuiteSparse/Matrix Market matrices, the latter on a single GPU. AIRG is the most robust on the PDE factors, with nearly flat iteration counts under refinement and no per-problem tuning, but has the largest setup and memory costs. GMRES polynomials are more robust than the Jacobi method at a similar cost. As the inner solve of an ILU preconditioner with tuned inner iteration counts, ISAI gives the largest median speedups over a hipSPARSE exact triangular solve (4.5 times and 6.8 times for ILU(0) and ILU(1)), though this was dominated by smaller problems; on the largest ILU(1) problems all four methods give similar median speedups of 2.1-2.6 times.
Sources
- A sparse approximate inverse for triangular matrices based on Jacobi iteration
- Neumann Series in GMRES and Algebraic Multigrid Smoothers
Related papers
- Do physics-informed neural networks (PINNs) need to be deep? Shallow PINNs using the Levenberg-Marquardt algorithm
- A Neural-preconditioned Poisson Solver for Mixed Dirichlet and Neumann Boundary Conditions
- Advanced Linear Algebra with Applications - Part I (Numerical linear algebra for PDEs, machine learning, and data assimilation)
- Operator learning meets inverse problems: A probabilistic perspective
- Second-order consistency for learning chaotic dynamics via randomized Jacobian matching
- Windowed thinning and query complexity for the bouncy particle and Zigzag samplers