A comparison of parallel iterative methods for ILU triangular solves
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× and 6.8× 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×.
Related
- Comparison of Algebraic Block Multi-Coloring and Leiden Methods for Parallel Preconditioning in the ICCG Method
- Accelerating Branch MPC with Two-Level Parallel Direct Solves on GPUs
- A Parallel Algebraic Multigrid Preconditioned Iterative Method Based on an MPI Process Grouping Strategy for Asynchronous Concurrent Execution of the Setup and Solve Phases
- Grad-div stabilized finite element Picard-Newton iterative methods for the Navier-Stokes equations
- Iterative Methods for Solving New Generalized Absolute Value Equations
BibTeX
@misc{dargaville2026comparison,
title = {{A comparison of parallel iterative methods for ILU triangular solves}},
author = {S. Dargaville and C. C. Pain},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00552},
eprint = {2611.00552},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00552},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A comparison of parallel iterative methods for ILU triangular solves
AU - S. Dargaville
AU - C. C. Pain
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00552
UR - https://arxiv.org/abs/2611.00552
AB - 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× and 6.8× 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×.
ER -