betaFeedback

WorksMathematics

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×\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.

Introduction

Incomplete LU (ILU) factorisations are often used as smoothers in multigrid methods or directly as preconditioners for difficult, sparse linear systems. ILU factorisations decompose a matrix A≈LUA \approx LU into two triangular factors while limiting fill-in (the setup phase). Hence an approximate solution to the linear system Ax=bAx=b can be found with x≈U−1L−1bx \approx U^{-1}L^{-1}b (the solve phase). Parallel algorithms for computing both phases are vital.

The setup phase can be parallelised by level-scheduling [41], which searches for sets of rows/columns that can be calculated independently of each other, or by the nonlinear fixed-point iteration of [11] (“ParILU”), which computes each entry of LL and UU independently and is now widely used on GPUs. The solve phase then requires the solution of two sparse triangular systems (SpTRSV). In serial this is very efficient, as forward/backward substitution (i.e., a Gauss–Seidel method in the triangular ordering) applies U−1U^{-1} and L−1L^{-1} exactly, but Gauss–Seidel methods are poorly suited to a parallel environment. Level-scheduling can be used [37, 41], as can synchronisation-free [27] or block/tiling algorithms [30]. Level-scheduling can have limited parallelism, as any one level set may not have enough unknowns to saturate the available parallelism and unknowns in other level sets must wait for updated unknowns to reach them; in general, exact solves of problems with triangular structure are not scalable in parallel.

Given this and the fact that ILU methods only produce approximate factorisations, parallel iterative methods with large tolerances are often used in the solve phase. LL and UU are nonsymmetric and often strongly non-normal; there is limited convergence theory available for iterative methods applied to such systems. It has been observed, however, that the triangular factors are often close to diagonally dominant

Funding: This work was supported by internal funding from the Department of Earth Science and Engineering, Imperial College London.

Applied Modelling and Computation Group, Imperial College London, SW7 2AZ, UK ([email protected]). for stable incomplete factorisations. Given this, a few iterations of a Jacobi method or sparse approximate inverses (SAIs) have proven very effective, as their application is very parallel and suited to GPUs [11, 3, 10, 45, 5, 29, 46], giving large speedups over exact triangular solves. Vendor sparse triangular solves continue to improve, however; on an AMD MI250X, [46] found the gain from iterative triangular solves in the ILU smoother of an AMG method was around 1.5×1.5\times.

While parallel implementations of algebraic multigrids are readily available, they have seen limited use replacing exact triangular solves as their convergence often degrades in nonsymmetric systems. In the last decade, however, reduction multigrids using AIR (Approximate Ideal Restriction) have been developed with excellent performance in nonsymmetric systems [35, 34, 33, 1, 50, 14, 15]. Recently we showed excellent weak scaling up to 11k GPUs when solving triangular (and near-triangular) systems from discretisations of advection problems with AIRG (Approximate Ideal Restriction with GMRES polynomials) [17].

In this work we compare four different parallel iterative methods for solving the triangular factors from ILU factorisations: a Jacobi method, an Incomplete Sparse Approximate Inverse (ISAI), GMRES polynomials, and AIRG. We test their robustness on difficult problems and their performance on a GPU, both when solving the factors alone and when used within an ILU preconditioner. We restrict ourselves to incomplete factorisations, as the factors from complete LU factorisations are typically much denser.

The main contributions of this paper are: (i) a new CF splitting algorithm for AIRG on GPUs, which produces a fine-fine block with a user-specified maximum diagonal dominance ratio (Section 6.2); (ii) the use of AIRG and GMRES polynomials to solve ILU triangular factors; and (iii) a comparison of the convergence, parallelism and GPU performance of these methods (Section 7). The new CF splitting and all of the iterative methods compared, along with cross-platform GPU implementations, are available in the open-source PFLARE2 library, which can be installed directly through the PETSc configure [6] with --download-pflare.

ILU factorisations

The quality of an ILU factorisation as a preconditioner depends heavily on the ordering of the unknowns [7], the fill-in allowed and any pivoting used; Chow and Saad [12] give an excellent characterisation of the properties that contribute to that quality. These choices affect the condition number, row scaling, diagonal dominance and normality of the resulting factors, and a poor ordering can produce L\mathbf{L} and U\mathbf{U} factors that are essentially unsolvable, sometimes even by direct methods. Our aim is not to examine how to produce good ILU factorisations, but rather how to iteratively solve the resulting factors (for nonsymmetric systems, how to reliably produce “good” approximate factorisations remains an open question), so we take several steps to improve the quality of L\mathbf{L} and U\mathbf{U}.

Before factorising, we left-scale the matrix by the inverse diagonal. We then loop through a number of different orderings and, for each, produce an ILU(0) or ILU(1) factorisation and use it as a preconditioner for GMRES(30) applied to the original system Ax=b\mathbf{A}\mathbf{x}=\mathbf{b}, with an exact triangular solve used to apply the factors. We select the ordering with the lowest iteration count among those that converge within 2000 iterations or, if none converge, the one with the lowest final relative residual, and use it for all subsequent solves; we note the winning ordering in the results. The orderings we try are: NATURAL, ND (nested dissection), RCM (reverse Cuthill–McKee), QMD (quotient minimum degree), 1WD (one-way dissection) and ROWLENGTH (orderings from PETSc), and COLAMD (column approximate minimum degree), MMD_ATA and MMD_AT_PLUS_A (multiple minimum degree on ATA\mathbf{A}^{\mathsf{T}}\mathbf{A} and AT+A\mathbf{A}^{\mathsf{T}}+\mathbf{A}), which are fill-reducing orderings from SciPy (see the start of Section SM3 of the supplementary materials for how these are extracted). Every ordering is applied symmetrically.

AIRG requires access to assembled sparse matrices, so we compute L\mathbf{L} and U\mathbf{U} explicitly with an exact level-based incomplete factorisation, ILU(kk); on the GPU we use the Kokkos Kernels [39, 48] spILUK implementation, which parallelises the factorisation with level-scheduling. The factorisation returns L\mathbf{L} as a unit lower-triangular matrix and U\mathbf{U} with the pivots on its diagonal, so we left-scale U\mathbf{U} by its inverse diagonal to give a unit diagonal, which typically improves the behaviour of the iterative solves applied to it (e.g., see [45] for an examination of different scaling approaches). We do not perform any pivoting, either when computing the factors or the orderings, so all of the matrices we test have nonzero diagonals, which the symmetric reorderings preserve; more robust ILU factorisations using pivoting are available. We now examine the iterative methods used to solve L\mathbf{L} and U\mathbf{U}, written for a generic system Ax=b\mathbf{A}\mathbf{x}=\mathbf{b} unless a specific property of the triangular factors is used.

ISAI

Sparse Approximate Inverses (SAIs) [25, 23, 13, 9] can be used to compute an approximation M≈A−1\mathbf{M} \approx\mathbf{A}^{-1}. A left inverse is computed by minimising ∥MA−I∥F2\lVert\mathbf{M}\mathbf{A}-\mathbf{I}\rVert_{\mathrm{F}}^2 over all M\mathbf{M} with a given sparsity pattern. This minimisation decouples into an independent least-squares problem for each row jj of M\mathbf{M} (or each column for a right inverse). We write J\mathcal{J} as the indices of the nonzero columns in the jjth row of A\mathbf{A} and I\mathcal{I} as the “shadow” of J\mathcal{J} (i.e., the indices of the nonzero columns in the rows of J\mathcal{J}) in A\mathbf{A}; the least-squares problem for row jj then only involves the small block A(J,I)\mathbf{A}(\mathcal{J},\mathcal{I}) and determines the nonzero entries M(j,J)\mathbf{M}(j,\mathcal{J}).

In this work we only use the “incomplete” SAI (ISAI) [5]; the incomplete version replaces the shadow I\mathcal{I} with J\mathcal{J}, so that the least-squares problem for each row becomes square and is solved exactly by

M(j,J)A(J,J)=I(j,J)(1)\mathbf{M}(j,\mathcal{J})\mathbf{A}(\mathcal{J},\mathcal{J})=\mathbf{I}(j,\mathcal{J}) \tag*{(1)}

for the entries of M\mathbf{M} in each row, jj. An ISAI is typically cheaper to form than a SAI as J⊆I\mathcal{J}\subseteq\mathcal{I}, and ISAIs can produce better preconditioners than SAIs [5]. We choose a sparsity pattern for M\mathbf{M} in advance, as this fixes the index sets J\mathcal{J} (and hence I\mathcal{I}) used in each row solve. In this work we build an assembled M\mathbf{M} with the sparsity pattern of A\mathbf{A} itself, rather than that of a higher power of A\mathbf{A}.

Jacobi method/Neumann polynomial

A simple iterative method for solving triangular factors is a Jacobi iteration. As noted in Section 2, both L\mathbf{L} and U\mathbf{U} have been scaled to have a unit diagonal, so for a generic triangular factor T∈{L,U}\mathbf{T}\in\{\mathbf{L},\mathbf{U}\} we can write T=I−G\mathbf{T}=\mathbf{I}-\mathbf{G}, where G=I−T\mathbf{G}=\mathbf{I}-\mathbf{T} is strictly triangular (strictly lower for L\mathbf{L}, strictly upper for U\mathbf{U}). Hence the Jacobi iteration for Tx=b\mathbf{T}\mathbf{x}=\mathbf{b} reduces to x(m+1)=Gx(m)+b\mathbf{x}^{(m+1)}=\mathbf{G}\mathbf{x}^{(m)}+\mathbf{b}, with iteration matrix G\mathbf{G}. Starting from a zero initial guess x(0)=0\mathbf{x}^{(0)}=\mathbf{0}, after mm iterations this gives

x(m)=∑j=0m−1Gjb=pm−1(T)b,pm−1(T)=I+G+⋯+Gm−1≈T−1,(2)\mathbf{x}^{(m)}=\sum_{j=0}^{m-1}\mathbf{G}^{j}\mathbf{b}=p_{m-1}(\mathbf{T})\mathbf{b},\qquad p_{m-1}(\mathbf{T})=\mathbf{I}+\mathbf{G}+\cdots+\mathbf{G}^{m-1}\approx\mathbf{T}^{-1}, \tag*{(2)}

which is the application of a Neumann polynomial of degree m−1m-1 [41, 11]. We use the two descriptions interchangeably in what follows. The Jacobi iteration requires only sparse matrix-vector products (SpMVs), so it is matrix-free, highly parallel and well suited to GPUs; this is the primary reason a few iterations of a Jacobi method have become a popular approximate triangular solve for ILU factorisations [11, 3, 10, 45]. The truncated series can also be assembled explicitly, with dropping, as a type of sparse approximate inverse [29].

Because G\mathbf{G} is strictly triangular it is nilpotent, with Gn=0\mathbf{G}^{n}=\mathbf{0} for a factor of size nn, so the Neumann series in (2) terminates exactly after nn terms and the spectral radius of the iteration matrix is zero. Asymptotic convergence is therefore trivially guaranteed, with the iteration exact after at most nn steps. This is misleading in practice, however, as we only ever apply a low-degree polynomial with m≪nm \ll n and a zero spectral radius says nothing about the size of Gm\mathbf{G}^{m} for small mm. When G\mathbf{G} is non-normal, as is typically the case for the factors of an ILU factorisation, ∥Gm∥\lVert\mathbf{G}^{m}\rVert can grow by many orders of magnitude before eventually decaying to zero, so a low-order Neumann polynomial can be highly inaccurate and the iteration can appear to diverge. The practical convergence is governed by the degree of non-normality of G\mathbf{G} and is better characterised by its pseudospectra or field of values than by its spectrum [47].

GMRES polynomial

Rather than fixing the coefficients to those of the Neumann series in (2) (which are all unity), a GMRES polynomial chooses them to minimise a residual. The GMRES polynomial of degree m−1m-1 written in a monomial basis (shown here for simplicity; we do not use this form as it is not numerically stable at high order) is

qm−1(A)=α0I+α1A+α2A2+…+αm−1Am−1≈A−1(3)q_{m-1}(\mathbf{A})=\alpha_{0}\mathbf{I}+\alpha_{1}\mathbf{A}+\alpha_{2}\mathbf{A}^{2}+\ldots+\alpha_{m-1}\mathbf{A}^{m-1}\approx\mathbf{A}^{-1} \tag*{(3)}

where the coefficients α\alpha are those implicitly constructed by mm steps of GMRES applied to Ax=b\mathbf{A}\mathbf{x}=\mathbf{b}; that is, x≈qm−1(A)b\mathbf{x}\approx q_{m-1}(\mathbf{A})\mathbf{b} is the GMRES iterate that minimises the residual ∥b−Aqm−1(A)b∥2\lVert\mathbf{b}-\mathbf{A}q_{m-1}(\mathbf{A})\mathbf{b}\rVert_{2} over the Krylov subspace [36, 28, 20]. We compute the GMRES polynomial in a Newton basis [28] once during the setup phase, from a single random right-hand side, and then reuse the same fixed polynomial for every subsequent application. This produces a stationary polynomial that can be applied matrix-free with only SpMVs (and no dot products), so, like the Neumann polynomial, it maps well onto GPUs.

AIRG

AIRG is a reduction multigrid built using the GMRES polynomials described in § 4; please see [35, 34, 33, 50, 14] for further details. An important feature of AIRG, in the context of the present work, is that it does not require a specific ordering of the unknowns, or any block or lower-triangular structure in the matrix, to be applied. Given this, all the components of AIRG are well suited to GPUs. The starting point of a reduction multigrid is a splitting of the unknowns into a set of “coarse” and “fine” points, with nC+nF=nn_C+n_F=n. This coarse/fine (CF) splitting allows us to write the block system

\begin{bmatrix} \mathbf{A}_{\mathrm{ff}} & \mathbf{A}_{\mathrm{fc}}\\ \mathbf{A}_{\mathrm{cf}} & \mathbf{A}_{\mathrm{cc}} \end{bmatrix} \begin{bmatrix} \mathbf{x}_{\mathrm{f}}\\ \mathbf{x}_{\mathrm{c}} \end{bmatrix} = \begin{bmatrix} \mathbf{b}_{\mathrm{f}}\\ \mathbf{b}_{\mathrm{c}} \end{bmatrix}, \tag*{(4)}\end{bmatrix}

and form prolongation and restriction operators of the form

P=[WI],R=[ZI].(5)\mathbf{P}=\begin{bmatrix}\mathbf{W}\\\mathbf{I}\end{bmatrix},\qquad\mathbf{R}=\begin{bmatrix}\mathbf{Z}&\mathbf{I}\end{bmatrix}. \tag*{(5)}

The ideal restrictor Z=−AcfAff−1\mathbf{Z}=-\mathbf{A}_{\mathrm{cf}}\mathbf{A}_{\mathrm{ff}}^{-1} enforces RA=0\mathbf{R}\mathbf{A}=\mathbf{0} on F-points, with the ideal prolongator W=−Aff−1Afc\mathbf{W}=-\mathbf{A}_{\mathrm{ff}}^{-1}\mathbf{A}_{\mathrm{fc}} enforcing AP=0\mathbf{A}\mathbf{P}=\mathbf{0} on F-points. The action of Aff−1\mathbf{A}_{\mathrm{ff}}^{-1} is in general dense and cannot be formed exactly. A practical reduction multigrid therefore replaces it with a sparse approximation A^ff−1≈Aff−1\widehat{A}_{\mathrm{ff}}^{-1} \approx A_{\mathrm{ff}}^{-1} and forms approximate ideal grid-transfer operators

Z=−AcfA^ff−1,W=−A^ff−1Afc.(6)Z = -A_{\mathrm{cf}}\widehat{A}_{\mathrm{ff}}^{-1}, \qquad W = -\widehat{A}_{\mathrm{ff}}^{-1}A_{\mathrm{fc}}. \tag*{(6)}

AIR methods typically only use ZZ in (6) and form a simpler approximation for WW [34]; we use a classical one-point prolongator, in which each F-point is interpolated with unit weight from its strongest C-point neighbour (the largest-magnitude entry in its row of AfcA_{\mathrm{fc}}). The coarse grid matrix is computed as Acoarse=RAPA_{\mathrm{coarse}} = RAP (which is an approximation to the Schur complement Acc−AcfA^ff−1AfcA_{\mathrm{cc}} - A_{\mathrm{cf}}\widehat{A}_{\mathrm{ff}}^{-1}A_{\mathrm{fc}}) and the procedure is applied recursively to build the multigrid hierarchy. To limit fill, entries of ZZ and of each coarse grid matrix smaller than a relative drop tolerance (10−410^{-4} and 10−610^{-6}, respectively) times the largest-magnitude entry in their row are removed.

AIRG uses the GMRES polynomial of § 4 applied to the fine-fine block as the approximate inverse, A^ff−1≈qm−1(Aff)≈Aff−1\widehat{A}_{\mathrm{ff}}^{-1} \approx q_{m-1}(A_{\mathrm{ff}}) \approx A_{\mathrm{ff}}^{-1}. This ensures that using AIRG in the solve phase only requires SpMVs. Note that approximations to Aff−1A_{\mathrm{ff}}^{-1} play two distinct roles in the multigrid: they are used to build the approximate ideal restrictor in (6), and also as an F-point smoother on the up cycle, with no C-point or down-smoothing required [14]. As in [14, 16], we use a single assembled matrix representation of qm−1(Aff)q_{m-1}(A_{\mathrm{ff}}) for both, with fill-in controlled by enforcing the sparsity of AffA_{\mathrm{ff}} on each of the matrix powers; the only polynomial we apply matrix-free is the higher-order coarse-grid solver described in § 5.4.

Good performance of AIRG with low-order GMRES polynomials depends on the CF splitting producing an AffA_{\mathrm{ff}} block that is amenable to a good sparse approximate inverse, which in practice means selecting fine rows that are as diagonally dominant as possible. We first place this requirement in the context of other multilevel methods, before detailing the CF splitting algorithm we use to ensure it.

Relationship to multilevel ILU

AIRG and other reduction multigrids are related to, but distinct from, multilevel ILU methods [40, 43, 42, 49]. Like reduction multigrids, multilevel ILU methods build a hierarchy by eliminating a leading submatrix on each level and deferring the remaining coupling to a Schur complement that is treated recursively. Obtaining parallelism in any of these methods typically begins with an independent set, and the canonical example is level-scheduling. For an ILU factorisation, level-scheduling is applied directly to the triangular factors LL and UU, parallelising both their setup and solve phases. Consider a lower-triangular factor LL: if we symmetrically permute LL (i.e., a reordering) so that each level set is contiguous, LL becomes block lower-triangular and, crucially, each diagonal block is itself diagonal, because the unknowns within a single level set do not reference one another. The unknowns in each block are those of one level set; the blocks must be processed sequentially (given the block lower-triangular structure), but all the unknowns within a block can be solved in parallel.

Viewed as a multilevel method, level-scheduling is one particular way of producing a diagonal AffA_{\mathrm{ff}} on every level. Any independent set of unknowns gives a diagonal AffA_{\mathrm{ff}}, as its members share no couplings; in general there are many such sets. The set used by level-scheduling is the maximal choice for which Afc=0A_{\mathrm{fc}} = 0, with its fine rows being the sources of the dependency graph and so having no sub-diagonal entries. The Schur complement Acc−AcfAff−1AfcA_{\mathrm{cc}} - A_{\mathrm{cf}}A_{\mathrm{ff}}^{-1}A_{\mathrm{fc}} then reduces to AccA_{\mathrm{cc}}, so no fill is produced and the reduced matrix remains triangular. Recursing produces level-scheduling exactly, i.e., the block Gaussian elimination of the forward substitution sweep. Level-scheduling sits at one end of a family of multilevel methods built on a diagonal Aff\mathbf{A}_{\mathrm{ff}}, which trade fill against the number of levels. Enforcing Afc=0\mathbf{A}_{\mathrm{fc}} = \mathbf{0} restricts each level to the current sources of the graph and so leaves as many levels as the critical path. Relaxing that requirement, keeping only the diagonal Aff\mathbf{A}_{\mathrm{ff}} of an independent set whose members need not be sources, permits larger F-blocks and fewer levels at the cost of fill in the Schur complement. Fewer levels than level-scheduling can also be had without fill in some cases; two examples are the partitioned inverse of [2] and cyclic reduction [22]. Alvarado and Schreiber [2] group consecutive columns of L\mathbf{L} into factors that are each invertible without fill, so that L−1\mathbf{L}^{-1} is applied exactly as a product of a few sparse factors. Because it is exact, how far the level sets can be merged is fixed by the sparsity of L\mathbf{L}, and the merged product form is only conditionally stable [24]. Cyclic reduction [22] uses a maximal independent set on each level, and remains fill-free when applied to tridiagonal systems. In general, larger Aff\mathbf{A}_{\mathrm{ff}} blocks and hence fewer levels allow more parallelism.

ILUM (ILU with multi-elimination) and its block version BILUM [40, 44] use a maximal independent set on matrices of general sparsity: the independent set still gives a diagonal/block-diagonal Aff\mathbf{A}_{\mathrm{ff}}, which is inverted trivially and exactly, but eliminating it now produces fill in the Schur complement that must be controlled by dropping. Later multilevel ILU methods such as [42] abandon diagonal Aff\mathbf{A}_{\mathrm{ff}} in search of even larger F-blocks and fewer levels. They instead select a non-diagonal Aff\mathbf{A}_{\mathrm{ff}} whose inverse is well behaved, in practice a diagonally dominant block. Such an Aff\mathbf{A}_{\mathrm{ff}} is no longer trivial to invert exactly, and so its inverse is itself only approximated, by an (incomplete) factorisation of Aff\mathbf{A}_{\mathrm{ff}}.

Both of these steps move the hierarchy away from an exact solve: dropping the fill makes the elimination incomplete and approximating Aff−1\mathbf{A}_{\mathrm{ff}}^{-1} makes the inversion inexact. The relevant distinction is therefore not whether the solve on each level is exact, but how the (inexact) inverse of Aff\mathbf{A}_{\mathrm{ff}} is applied. In these multilevel ILU methods the approximate A−1\mathbf{A}^{-1} is built from (incomplete) triangular factors and applied by a triangular solve, so the parallelism available on each level is once again governed by the sparsity structure and ordering of those factors, reintroducing the level-set problem we began with. We also note that these multilevel ILU methods are built for and applied to the original matrix A\mathbf{A}; each is a self-contained multilevel preconditioner for A\mathbf{A}, rather than a means of solving an already-computed triangular factor. Multilevel ILU methods could be used to solve already-computed triangular factors, but this would mean computing a further ILU factorisation of L\mathbf{L} or U\mathbf{U} and a triangular solve on every level, which is both redundant and exposes less parallelism.

In contrast, AIRG applied to either the original matrix A\mathbf{A} or to the triangular factors L\mathbf{L} and U\mathbf{U} typically retains more parallelism. It does this by coarsening based on the same idea as in the multilevel ILU of [42], targeting the extraction of a diagonally dominant non-diagonal Aff\mathbf{A}_{\mathrm{ff}} (with an algorithm detailed in Section 6.2), but then applying the approximate inverse of Aff\mathbf{A}_{\mathrm{ff}} as a GMRES polynomial rather than by a triangular solve. The essential point of AIRG (or of an equivalent multilevel LDU/Schur-complement scheme built on a GMRES polynomial approximation of Aff−1\mathbf{A}_{\mathrm{ff}}^{-1}) is that at no point does the parallelism on any level depend on the ordering of the unknowns. The price of this is robustness; multilevel ILU factorizations applied to the original matrix A\mathbf{A} are typically very robust, as they can utilise much of the literature around producing good ILU factorisations in difficult problems, whereas convergence theory and practical guidance for GMRES (and therefore GMRES polynomials) is less developed. In this work we focus on the SpTRSV problem: ILU factorisations are widely used, robust and readily available on GPUs, so we take the L\mathbf{L} and U\mathbf{U} factors they have already (robustly) produced as given and use AIRG to solve them. We leave a study of applying AIRG to A\mathbf{A} directly in these problems for future work. We now consider a parallel CF splitting algorithm for producing diagonally dominant Aff\mathbf{A}_{\mathrm{ff}}.

DIAG_DOM CF splitting

In our previous work [16] we introduced the PMISR DDC algorithm (Parallel Modified Independent Set for Reduction multigrids and Diagonal Dominance Cleanup) in order to produce diagonally dominant Aff\mathbf{A}_{\mathrm{ff}} blocks. The first pass, PMISR, is a slight modification of PMIS (the Parallel Modified Independent Set algorithm of [19]) that computes an independent set in S+ST\mathbf{S}+\mathbf{S}^{\mathrm{T}} (where S\mathbf{S} is the classical strength-of-connection matrix, in which an off-diagonal entry AijA_{ij} is strong if ∣Aij∣≥θmax⁡k≠i∣Aik∣\lvert A_{ij}\rvert\geq\theta\max_{k\ne i}\lvert A_{ik}\rvert for a strength threshold θ\theta) such that no large off-diagonal entries appear in the resulting Aff\mathbf{A}_{\mathrm{ff}}. The second pass, DDC, then flips the F rows with the worst diagonal dominance back to C. We define the diagonal dominance ratio of an F row ii restricted to the F columns as

rdd(i)=∑j∈F, j≠i∣Aij∣∣Aii∣,F={i:c(i)=F},(7)r_{\mathrm{dd}}(i)=\frac{\sum_{j\in\mathcal{F},\,j\ne i}\lvert A_{ij}\rvert}{\lvert A_{ii}\rvert},\qquad\mathcal{F}=\{i:c(i)=\mathrm{F}\}, \tag*{(7)}

where c\mathbf{c} is the vector of C/F markers. The DDC pass takes a user-specified local fraction ff and swaps at least the fnFfn_{\mathrm{F}} worst F rows (by rddr_{\mathrm{dd}}) back to C; in our implementation it also always swaps every F row with rdd≥1r_{\mathrm{dd}}\geq1, so the resulting Aff\mathbf{A}_{\mathrm{ff}} is always diagonally dominant.

For discretisations of advection-dominated PDEs we have found this gives an Aff\mathbf{A}_{\mathrm{ff}} that is sufficiently diagonally dominant for AIRG to converge well. PMISR DDC, however, gives no control over how diagonally dominant Aff\mathbf{A}_{\mathrm{ff}} is beyond the fixed bound of one, while the fraction ff of additional rows flipped is a problem-dependent parameter. This is suboptimal for the triangular factors considered in this work, where a stronger bound can be needed (§ 5.3). To improve robustness we therefore introduce a variant of PMISR DDC that iterates to a user-specified target τ\tau on the maximum diagonal dominance ratio across all rows of Aff\mathbf{A}_{\mathrm{ff}}; we refer to this as the DIAG_DOM splitting. Selecting the largest subset of rows of a matrix whose diagonal dominance ratios are below a given threshold is NP-complete [32] and hence we do not pursue an exact solution. Heuristics for determining diagonally dominant submatrices have been investigated within the context of different multilevel methods [43, 42, 32, 31, 51, 16, 17].

We follow on from this previous work directly and seek a parallel algorithm that avoids any inherently sequential selection. As such we only use maximal independent set algorithms as our building blocks. An outline of our algorithm is to start with a first pass which selects candidate F-points and then rely on a number of iterations after this to reject “bad” F-points. The two phases pursue different objectives, and our measure choices reflect this.

The first pass selects on connectivity in S+ST\mathbf{S}+\mathbf{S}^{\mathrm{T}} rather than on rddr_{\mathrm{dd}} directly. Typically we find the hard loss of diagonal dominance is driven by clusters of mutually large, comparable off-diagonal entries competing for the same diagonal budget; the connectivity graph of S+ST\mathbf{S}+\mathbf{S}^{\mathrm{T}} encodes exactly this competition, so a maximal independent set thins each cluster in a single pass while also favouring the low-connectivity rows whose elimination keeps the coarse-grid matrix sparse. A measure based on rddr_{\mathrm{dd}} achieves neither, and we found that using rddr_{\mathrm{dd}} as the first-pass measure substantially increased the number of rejection iterations.

Hence our DIAG_DOM CF splitting consists of a first pass of PMISR with S+ST\mathbf{S}+\mathbf{S}^{\mathrm{T}}, where S\mathbf{S} is formed from A\mathbf{A} with the strength threshold set to θ=τ\theta= \tau, the target diagonal dominance ratio, so that DIAG_DOM has a single parameter. The rejection step then iterates as many times as required, converting F-points to C until the resulting Aff\mathbf{A}_{\mathrm{ff}} meets the target τ\tau. Swapping rows one at a time would trivially allow this, but would not be sufficiently parallel.

Instead, on each iteration we compute an independent set over the F rows that do not yet satisfy rdd<τr_{\mathrm{dd}} < \tau, using the same PMISR routine as in the first pass on Aff+AffT\mathbf{A}_{\mathrm{ff}}+\mathbf{A}_{\mathrm{ff}}^{\mathsf{T}}, and swap its members to C. This swaps many non-adjacent F-points simultaneously, but ensures that for any pair of strongly coupled F-F points, only one is swapped per iteration; the neighbours whose rddr_{\mathrm{dd}} improves as a result are re-evaluated on the next iteration. As PMISR selects the rows with the smallest measure, we invert rddr_{\mathrm{dd}} and use the measure

μ(i)=M−rdd(i)+δξ(i),(8)\mu(i) = M - r_{\mathrm{dd}}(i) + \delta\xi(i), \tag*{(8)}

where ξ(i)∈[0,1)\xi(i) \in[0,1) is a random value used for tie-breaking and δ=10−10\delta= 10^{-10} is small enough not to change the relative ordering of rows with distinct rddr_{\mathrm{dd}}. The constant M≥max⁡irdd(i)+1M \ge\max_i r_{\mathrm{dd}}(i) + 1 keeps μ(i)≥1\mu(i) \ge1, as PMISR would otherwise classify a row with ∣μ∣<1|\mu| < 1 (normally a row with no strong neighbours) directly as F. Rows already satisfying rdd<τr_{\mathrm{dd}} < \tau are assigned μ=+∞\mu= +\infty and are never swapped. We also tried measuring strength relative to the diagonal in the first pass, ∣Aij∣≥τ∣Aii∣|A_{ij}| \ge\tau|A_{ii}|, and scaling rddr_{\mathrm{dd}} by the inverse of the number of F-F neighbours to keep Aff\mathbf{A}_{\mathrm{ff}} sparser [42]; the former gave a worse first pass that required considerably more work in the rejection step, and the latter gave no large improvement, as our first pass already targets this objective.

The freeze of already-satisfied rows ensures the rejection iterations terminate. Flipping any F row to C only ever removes terms from another row’s F-F sum in (7), so rddr_{\mathrm{dd}} is monotone non-increasing for every surviving row; a row that already satisfies the target therefore stays satisfied. Each iteration strictly decreases the number of rows violating the target, so the loop cannot continue indefinitely and terminates once every row meets τ\tau. In the worst case this termination may take as many iterations as there are F-points produced by the first pass, but in practice we find that for sparse factors only a few iterations are required.

This is summarised in Algorithm 6.1. The use of an implicit transpose lets us pass Aff\mathbf{A}_{\mathrm{ff}} directly to the independent set algorithm without ever forming Aff+AffT\mathbf{A}_{\mathrm{ff}}+\mathbf{A}_{\mathrm{ff}}^{\mathsf{T}} explicitly. The whole algorithm is well suited to GPUs: the diagonal dominance ratio is embarrassingly parallel to compute and the only global reduction required is a single max over rddr_{\mathrm{dd}} across all F rows per iteration. Each iteration involves computing an independent set, for which efficient GPU implementations are available [38, 21].

Comparison of CF splittings

In this section we show that the DIAG_DOM CF splitting in Algorithm 6.1 can enforce a maximum diagonal dominance ratio while retaining a similar number of F-points to PMISR DDC. For many problems derived from PDEs, PMISR DDC can produce a sufficiently diagonally dominant block cheaply (as there is only one “rejection” step) and hence AIRG converges well. For more difficult problems, however, we find that DIAG_DOM is more robust. For DIAG_DOM we set τ=0.5\tau= 0.5. For the PMISR DDC algorithm we use the same first pass as DIAG_DOM, but for the second pass we do a single DDC iteration with f=0.1f = 0.1; this converts at least the worst 10% of F-points to C-points, measured by rddr_{\mathrm{dd}}, along with every F-point with rdd≥1r_{\mathrm{dd}} \ge1.

We show this for an example test matrix BCSSTK24 from the SuiteSparse collection. First we reorder the matrix with an RCM ordering and produce an ILU(0)

Algorithm 6.1 DIAG_DOM CF splitting iteration.

Require: Matrix A\mathbf{A}, initial C/F markers c\mathbf{c} from first-pass PMISR on S+ST\mathbf{S} + \mathbf{S}^{\mathsf{T}}, target ratio τ\tau

  1. loop

  2. Extract Aff\mathbf{A}_{\mathrm{ff}} from A\mathbf{A} using c\mathbf{c} ▷ F rows and F columns of A\mathbf{A}

  3. Compute rdd(i)r_{\mathrm{dd}}(i) for every i∈Fi \in\mathcal{F} ▷ Eq. (7)

  4. rmax⁡←max⁡i∈Frdd(i)r_{\max} \leftarrow\max_{i \in\mathcal{F}} r_{\mathrm{dd}}(i) over all ranks ▷ Global reduction

  5. if rmax⁡<τr_{\max} < \tau then exit ▷ Aff\mathbf{A}_{\mathrm{ff}} meets the target

  6. Initialise swap markers s(i)←s(i) \leftarrow candidate for every i∈Fi \in\mathcal{F}

  7. for i∈Fi \in\mathcal{F} in parallel do

  8. if rdd(i)<τr_{\mathrm{dd}}(i) < \tau then

  9. μ(i)←+∞\mu(i) \leftarrow+\infty; s(i)←s(i) \leftarrow keep ▷ Already satisfied, never swapped

  10. else

  11. μ(i)←M−rdd(i)+δξ(i)\mu(i) \leftarrow M - r_{\mathrm{dd}}(i) + \delta\xi(i) ▷ Eq. (8)

  12. end if

  13. end for

  14. Run PMISR on Aff+AffT\mathbf{A}_{\mathrm{ff}} + \mathbf{A}_{\mathrm{ff}}^{\mathsf{T}} with measure μ\mu ▷ Largest rddr_{\mathrm{dd}} first

  15. s(i)←s(i) \leftarrow swap for every candidate ii in the resulting independent set

  16. for i∈Fi \in\mathcal{F} in parallel do

  17. if s(i)=s(i) = swap then

  18. Flip c(i)c(i) from F to C

  19. end if

  20. end for

  21. end loop

factorisation of the matrix. We then run the CF splitting algorithms on the L\mathbf{L} factor (similar results are found for U\mathbf{U}); this gives the Aff\mathbf{A}_{\mathrm{ff}} that would be used on the top level of the AIRG multigrid applied to L\mathbf{L}. For consistency we refer to the submatrix as Aff\mathbf{A}_{\mathrm{ff}} rather than Lff\mathbf{L}_{\mathrm{ff}}.

Figure 1 shows that the matrix L\mathbf{L} is not diagonally dominant, with many rows having rdd>1r_{\mathrm{dd}} > 1. For this matrix, the PMISR DDC algorithm results in a diagonally dominant Aff\mathbf{A}_{\mathrm{ff}} matrix, with a maximum rddr_{\mathrm{dd}} equal to 0.998. The DIAG_DOM algorithm, however, gives an Aff\mathbf{A}_{\mathrm{ff}} matrix which is much more diagonally dominant; the maximum rddr_{\mathrm{dd}} is just below 0.5 (0.500 to three decimal places), which matches the maximum provided threshold τ=0.5\tau= 0.5. Both CF splittings produce Aff\mathbf{A}_{\mathrm{ff}} matrices of similar sizes for this matrix. PMISR DDC gives 788 F-points, with DIAG_DOM giving 744 F-points; this is approximately 21–22% of the unknowns (of n=3562n = 3562). The difference shows in the convergence of AIRG, which applies the CF splitting on every level of the hierarchy. On the ILU(0) factors of bcsstk24 AIRG takes 5 iterations on both L\mathbf{L} and U\mathbf{U} with either splitting, but on the harder L\mathbf{L} factor from ILU(1) it takes 18 iterations with PMISR DDC, compared with 6 with DIAG_DOM (both take 5 on U\mathbf{U}).

Binned diagonal dominance ratio for each row in the lower-triangular factor L

Figure 1. Binned diagonal dominance ratio, rddr_{\mathrm{dd}}, for each row in the lower-triangular factor L produced from an ILU(0) factorisation of the matrix BCSTK24. The maximum rddr_{\mathrm{dd}} across any row in L is 11137 (i.e., L is far from diagonally dominant), but all rows with rdd≥1r_{\mathrm{dd}} \ge1 have been added to the top bin in the figure. The ratio is also shown for the Aff\mathbf{A}_{\mathrm{ff}} submatrices resulting from a PMISR DDC and DIAG DOM CF splitting on L.

Table 1 shows the effect of sweeping τ\tau for the DIAG_DOM splitting applied to the same L\mathbf{L} factor of bcsstk24. In every case the achieved maximum rddr_{\mathrm{dd}} matches the requested target τ\tau to within a tight tolerance. As τ\tau is decreased the resulting Aff\mathbf{A}_{\mathrm{ff}} becomes smaller, ranging from around 28% of the unknowns at τ=0.9\tau= 0.9 down to around 12% at τ=0.1\tau= 0.1. A larger τ\tau therefore produces a larger Aff\mathbf{A}_{\mathrm{ff}}, but the resulting block is less diagonally dominant and hence harder to approximate, which degrades the convergence of the resulting AIRG. Conversely, a smaller τ\tau gives a more diagonally dominant (and more easily inverted) Aff\mathbf{A}_{\mathrm{ff}}, but extracts fewer F-points on each level. We discuss the implications of this trade-off for parallelism below.

τ\taumax rddr_{\mathrm{dd}}size(Aff\mathbf{A}_{\mathrm{ff}})% of unknowns
0.10.10041811.73
0.20.19852414.71
0.30.29859916.82
0.40.39870919.90
0.50.50074420.89
0.60.59881522.88
0.70.69887424.54
0.80.79794826.61
0.90.897101228.41

Table 1. Effect of varying the target diagonal dominance ratio τ\tau in the DIAG DOM CF splitting, applied to the L factor from an ILU(0) factorisation of BCSTK24. The achieved maximum rddr_{\mathrm{dd}} is rounded to three decimal places; every value is strictly below its τ\tau.

Parallelism

For AIRG, as noted in § 5.2, τ\tau controls how diagonally dominant, and hence how large, the resulting Aff\mathbf{A}_{\mathrm{ff}} block is on each level, and we noted in § 5.1 that the size of Aff\mathbf{A}_{\mathrm{ff}} sets the available parallelism. A large Aff\mathbf{A}_{\mathrm{ff}} on each level, paired with an approximation of Aff−1\mathbf{A}_{\mathrm{ff}}^{-1} that can be applied with only SpMVs, ensures there is sufficient fine-grained parallelism within the SpMVs on each level, and also gives fewer levels in the hierarchy. Many levels are undesirable, particularly on GPUs: each level requires a synchronisation and kernel launches on ever smaller coarse-grid systems, and the Schur complement coarse-grid matrices tend to become denser (there is fill-in even with dropping), giving more communication than work when distributed on lower levels. There is, however, no guarantee for a general linear system that a large diagonally dominant Aff\mathbf{A}_{\mathrm{ff}} can be extracted on every level; for a dense L or U with entries all of similar magnitude the hierarchy can degenerate into a single-unknown Gaussian elimination with no parallelism, so reduction multigrids are best suited to sparse factors.

Increasing τ\tau is one mechanism for reducing the number of levels, with another being the automatic truncation of the multigrid hierarchy we introduced in [17], which removes the coarsest levels, namely those with the least parallelism. On each level during the setup we generate a high-order GMRES polynomial as a tentative coarse-grid solver and test whether it can solve the coarse-grid problem to a loose relative tolerance against a random right-hand side; if it can, we truncate the hierarchy on that level and use the polynomial as the coarse-grid solver. We are able to truncate in this way precisely because AIRG only requires an approximate solve on each level. Truncation trades additional work for more parallelism (and a less dense communication pattern), typically resulting in a faster solve time.

Much as the number of level sets limits the parallelism of an exact triangular solve, the parallelism available in a multilevel hierarchy is problem-dependent. A level-set substitution must process its level sets in sequence, with the rows within each level set processed in parallel. Similarly, an AIRG hierarchy is an ordered sequence of levels, as the F-point smoothing on each level must be completed before proceeding to the next, while with an SpMV-based application of an Aff−1A_{\mathrm{ff}}^{-1} approximation all the F-points on a level are smoothed in parallel. We therefore compare the number of level sets of a factor with the number of levels in its AIRG hierarchy. These counts are not directly comparable: each level of a V-cycle applies a small, fixed number of SpMVs (with the assembled qm−1(Aff)q_{m-1}(A_{\mathrm{ff}}), AfcA_{\mathrm{fc}}, RR and PP), each of which is fully parallel, so the number of sequential kernels in an AIRG application is a small multiple of the number of levels, compared with one per level set for a level-set solve. The actual cost of both is measured by the GPU timings in § 6.4.2. The ILU(0) of bcsstk24 has 856 level sets in a natural ordering and 486 in rcm, an average of 4.2 and 7.3 rows per level set, respectively. For the LL factor, AIRG with the DIAG DOM CF splitting and auto-truncation produces a hierarchy of only 24 levels, with 744 F-points (21% of the unknowns) on the top grid.

These counts also behave differently under refinement. The number of levels in an untruncated multigrid hierarchy grows like O(log⁡n)O(\log n) with the number of unknowns nn, while the number of level sets of a triangular factor can grow much faster; we give an example in § 6.2. A multilevel approach based on extracting diagonally dominant submatrices can therefore require far fewer sequential steps than a level-set approach in problems where the latter is close to serial (e.g., 1D upwind advection). We examine this below by reporting the number of level sets of and AIRG levels on several test problems.

Results

Unless otherwise noted, each factor LL or UU is solved with an undamped Richardson iteration preconditioned by the method we are testing. We monitor the unpreconditioned residual norm, use a random right-hand side, a zero initial guess, a relative tolerance of 10−610^{-6} and a maximum of 2000 iterations. One iteration is therefore one V-cycle of AIRG, one application of the GMRES polynomial or of the ISAI, or one Jacobi sweep. The cost of an iteration differs between the methods: a Jacobi sweep requires one SpMV with the factor, an ISAI iteration one SpMV with the factor and one with the approximate inverse (which has the same sparsity), a GMRES polynomial iteration seven SpMVs with the factor (we use 6th-order polynomials), and an AIRG V-cycle several SpMVs on each level of its hierarchy. The parameters used for AIRG and the other iterative methods are fixed across all problems tested in this paper unless otherwise noted; the full set of solver and preconditioner options for PETSc and PFLARE is given in Section SM1 of the supplementary materials. Given that iterative methods in non-normal systems can appear to diverge before converging, we must take care when interpreting convergence results. We therefore define divergence as occurring when a relative residual norm grows by more than 10410^4.

We consider two standard multigrid metrics when discussing AIRG: the grid complexity, defined as the total number of unknowns across all levels divided by the number on the finest level, and the storage complexity, defined as the total number of nonzeros in the operators that must be stored to apply a multigrid cycle divided by the number of nonzeros in the finest-level matrix (a proxy for the memory required by the hierarchy). As we only use F-point smoothing, the full operator on each level is not required during the solve; the stored operators on each level are AffA_{\mathrm{ff}}, AfcA_{\mathrm{fc}}, A^ff−1\hat{A}_{\mathrm{ff}}^{-1}, RR and PP, along with the coarsest matrix, so the storage complexity can be below one.

We begin by testing on three families of matrices directly from discretisations of PDEs often used as examples in the ILU literature, focusing on the achieved convergence. We sweep the grid size and parameter values; these are listed in Sections 7.1 to 7.3. In all three cases the PDE is defined for a scalar unknown field u(x,y)u(x,y) with a given source term f(x,y)f(x,y) on the unit square Ω=(0,1)2\Omega=(0,1)^2, with Dirichlet boundary conditions. We assemble the discrete operator only on the N×NN \times N interior nodes of a uniform grid with spacing h=1/(N+1)h=1/(N+1). The unknowns are assembled with the natural lexicographic ordering ℓ=jN+i\ell=jN+i for i,j∈{0,…,N−1}i,j\in\{0,\ldots,N-1\}, where ii indexes the xx-direction and jj the yy-direction.

Indefinite Helmholtz

The shifted Helmholtz problem is

−∂2u∂x2−∂2u∂y2−k2u+ηu=fon Ω,(9)-\frac{\partial^2 u}{\partial x^2}-\frac{\partial^2 u}{\partial y^2}-k^2u+\eta u=f \quad\text{on }\Omega, \tag*{(9)}

where kk is the (real) wavenumber and η≥0\eta\ge0 is a real shift. We discretise with a second-order 5-point central-difference stencil. The matrix is symmetric but indefinite, becoming more indefinite as η→0\eta\to0. Rather than fix kk in absolute terms, we parameterise the problem by the number of points per wavelength, ppw, and a shift percentage ss, with

k=2πppw⋅h,η=s100k2.(10)k=\frac{2\pi}{\mathrm{ppw}\cdot h}, \qquad\eta=\frac{s}{100}k^2. \tag*{(10)}

Fixing ppw across refinements means the wavelength always spans the same number of cells, so the problem is equally well resolved at every NN; without this rescaling, refining the grid would make the problem easier (more points per wavelength). With ppw fixed, grid refinement isolates the effect of the discrete problem size on the solver.

We sweep the grid size N∈{100,200,450,800}N\in\{100,200,450,800\} for ppw =10=10 with s∈{0,5,50}s\in\{0,5,50\}, and for ppw =4=4 with s=0s=0 only, the fully indefinite case, which is the hardest problem in this family. For the ILU(0) factorisation every method converges robustly across the entire sweep, so we don’t include its table. AIRG takes the fewest iterations, between 1 and 3, independent of NN, the wavenumber and the shift, while the iteration counts of the other methods are also essentially flat under refinement (with Jacobi the largest, at up to 37 iterations).

The contrast appears for the ILU(1) factorisation, for which Table 2 gives the iteration count required to solve the LL and UU factors. For ppw =10=10 all methods again converge with roughly constant iteration counts under refinement. For the fully indefinite, under-resolved ppw =4=4, s=0s=0 case, however, the additional fill produces L and U factors that are much harder to solve iteratively, and the simpler methods degrade as the grid is refined. Jacobi diverges at every grid size. The GMRES polynomial converges only on the coarsest grid, and then only after more than 1700 iterations, hitting the maximum iteration count for every N≥200N \ge200. ISAI is fairly resilient, converging for N=100N = 100 and N=200N = 200 before diverging for N≥450N \ge450. AIRG, by contrast, converges in just 3 iterations at every grid size. This is the only Helmholtz case in which the simpler iterative methods fail, with AIRG the only method that remains robust throughout.

ppws (%)NorderingAIRG LAIRG UGMRES poly LGMRES poly UISAI LISAI UJacobi LJacobi U
40100qmd33175419011821DIVDIV
40200qmd33MAXMAX2324DIVDIV
40450qmd33MAXMAXDIVDIVDIVDIV
40800qmd33MAXMAXDIVDIVDIVDIV
100100colamd335516153130
100200colamd337619173735
100450mmd_ata338824224845
100800nd325515143029
105100nd324412112423
105200colamd336617163533
105450mmd_ata337720204342
105800mmd_ata337721194240
1050100rcm33131335357373
1050200rcm33131335357474
1050450natural33131336367575
1050800natural33131336367575

Table 2. For the indefinite Helmholtz problem (7.1) the number of iterations to solve the L and U factors generated by an ILU(1) factorisation to a relative tolerance of 10−610^{-6}, as the grid is refined for each combination of points per wavelength ppw and shift ss. “MAX” denotes hitting the maximum iteration count (2000) and “DIV” indicates the solve diverged.

Advection-diffusion

We follow [11] and consider the advection-diffusion problem

−∂2u∂x2−∂2u∂y2+βeff∂(exyu)∂x+βeff∂(e−xyu)∂y=fon Ω,(11)-\frac{\partial^2 u}{\partial x^2} - \frac{\partial^2 u}{\partial y^2} + \beta_{\mathrm{eff}}\frac{\partial(e^{xy}u)}{\partial x} + \beta_{\mathrm{eff}}\frac{\partial(e^{-xy}u)}{\partial y} = f \quad\text{on } \Omega, \tag*{(11)}

where βeff≥0\beta_{\mathrm{eff}} \ge0 is the advection coefficient that controls the strength of the convective term. The advection field v(x,y)=(exy,e−xy)\mathbf{v}(x,y) = (e^{xy},e^{-xy}) is variable across the domain. We discretise both the diffusion and the advection terms with second-order central differences, giving a 5-point stencil. Central differencing of the advection term is used deliberately: for large β\beta it produces strongly nonsymmetric matrices far from diagonally dominant, whose ILU factors can be unstable, a standard hard test for ILU preconditioners [11].

To isolate the effect of grid refinement, we hold the cell Péclet number constant under refinement by setting

βeff=β⋅hrefh,(12)\beta_{\mathrm{eff}} = \beta\cdot\frac{h_{\mathrm{ref}}}{h}, \tag*{(12)}

where href=1/(Nref+1)h_{\mathrm{ref}} = 1/(N_{\mathrm{ref}}+1) is a fixed reference spacing with Nref=450N_{\mathrm{ref}} = 450 (the reference grid in [11]). We sweep the grid size N∈{100,200,450,800}N \in\{100, 200, 450, 800\} for each advection strength β∈{1500,3000,10000}\beta\in\{1500, 3000, 10000\}; the values used in [11] correspond to β∈{1500,3000}\beta\in\{1500, 3000\} with N=450N = 450. Table 3 gives the number of iterations required to solve the L\mathbf{L} and U\mathbf{U} factors for the ILU(1) factorisation; we summarise the ILU(0) results in the text rather than including a table.

β\betaNNorderingAIRG LAIRG UGMRES poly LGMRES poly UISAI LISAI UJacobi LJacobi U
1500100rcm5364310310DIV19
200rcm631193DIV10DIV20
450natural521893DIV8DIV18
800natural723273DIV8DIV18
3000100rcm54696DIV27DIV80
200rcm741276DIV28DIV83
450rcmDIV4DIV6DIV28DIV85
8001wd3510942102DIVDIV
10000100rcm777820DIVDIVDIVDIV
200rcm9714224DIVDIVDIVDIV
450rcm12729826DIVDIVDIVDIV
800rcm17851227DIVDIVDIVDIV

Table 3. For the advection-diffusion problem (7.3) the number of iterations to solve the L and U factors generated by an ILU(1) factorisation to a relative tolerance of 10−610^{-6}, as the grid is refined for each advection strength β\beta. “MAX” denotes hitting the maximum iteration count (2000) and “DIV” indicates the solve diverged.

For the ILU(0) factorisation AIRG is robust and largely insensitive to refinement, converging in between 1 and 6 iterations across the whole sweep, with every method converging for every β\beta and NN. The other methods, by contrast, are not scalable under refinement: for β=3000\beta= 3000 the Jacobi iteration count on the L/U\mathbf{L}/\mathbf{U} factors grows from 79/36 at N=100N = 100 to 144/206 at N=800N = 800, and ISAI similarly grows from 40/18 to 72/103, whereas AIRG stays between 3 and 6 iterations.

The ILU(1) factorisation (Table 3) is far more challenging. The additional fill makes the L\mathbf{L} factor in particular very hard to solve: Jacobi diverges on the L\mathbf{L} factor for every β\beta and NN (and on both factors for β=10000\beta= 10000 and for β=3000\beta= 3000, N=800N = 800), and ISAI diverges on L\mathbf{L} across almost the entire sweep. GMRES polynomials avoid divergence in all but one case (noted below) but are not scalable, with the L\mathbf{L} iteration count growing steeply under refinement, from 64 to 327 for β=1500\beta= 1500 and from 78 to 512 for β=10000\beta= 10000. AIRG is the only method that solves both factors with a low, near-constant iteration count throughout, taking 2–7 iterations for β=1500\beta= 1500 and β=3000\beta= 3000 and growing only mildly (from 7 to 17) for the hardest β=10000\beta= 10000 case; the lone exception is β=3000\beta= 3000, N=450N = 450, where both AIRG and GMRES polynomials diverge on L\mathbf{L} in the chosen ordering. The rcm ILU(1) factor L\mathbf{L} at this size is far less stable than at N=200N = 200 (∥L−1b∥/∥b∥\lVert\mathbf{L}^{-1}\mathbf{b}\rVert/\lVert\mathbf{b}\rVert reaches 10610^6 for a random b\mathbf{b}, compared with 180), and the residual of both methods initially grows by more than our divergence threshold of 10410^4. With the divergence check disabled, AIRG converges in 12 iterations and the GMRES polynomial in 272. We nonetheless count this as a failure: a single V-cycle (or a few iterations of the other methods) that amplifies the residual is of little use as a fixed-work inner solve for Ax=b\mathbf{A}\mathbf{x} = \mathbf{b} (§ 6.4.2).

The iteration counts above are reported for the ordering that is best for the exact factorisation, chosen afresh at each NN (as noted in § 1); advection-dominated problems are well known to be sensitive to ordering due to long-range transport, and this choice can change the difficulty of the iterative factor solves considerably. For β=3000\beta= 3000 the ordering changes from RCM to 1WD at N=800N = 800, as the RCM ILU(1)-preconditioned Ax=b\mathbf{A}\mathbf{x} = \mathbf{b} solve diverges; this, rather than the grid size, is responsible for the drop in the GMRES polynomial iteration count on L\mathbf{L} from 127 at N=200N = 200 to 10 at N=800N = 800. The 1WD factors are considerably easier for every iterative method, though worse as a preconditioner when solved exactly (the exact ILU(1)-preconditioned solve takes 36 to 350 iterations, compared with 18 to 119 for RCM up to N=450N = 450). With 1WD fixed at every NN, AIRG solves the factors in 3 and 5 iterations independent of NN, whereas the GMRES polynomial grows from 7 to 10 iterations on L\mathbf{L}, ISAI from 48 to 102 on U\mathbf{U}, and Jacobi diverges on both factors from N=450N = 450. Conversely, for β=1500\beta= 1500, where the chosen ordering at N=450N = 450 and 800 is NATURAL, fixing RCM instead gives ILU(1) factors L\mathbf{L} on which AIRG and the GMRES polynomial also diverge at those sizes.

Table 4 isolates the effect of the ordering for the β=10000\beta= 10000, N=100N = 100, ILU(0) problem. Of the nine orderings we tested, only three (QMD, ND and COLAMD) produce an ILU(0) factorisation for which the Ax=b\mathbf{A}\mathbf{x} = \mathbf{b} solve with exact triangular solves converges, so we restrict the comparison to these. Across all three, AIRG solves both factors in 1 to 3 iterations, whereas the iteration counts on L/U\mathbf{L}/\mathbf{U} of the GMRES polynomials range from 1/1 under ND to 37/16 under COLAMD, those of ISAI from 3/4 to 58/45, and those of Jacobi from 6/6 to 115/90. The choice of ordering, made for the exact factorisation, increases the difficulty of the factor solves by more than an order of magnitude for the single-level methods but leaves AIRG largely unaffected for these ILU(0) factors.

orderingAIRG LAIRG UGMRES poly LGMRES poly UISAI LISAI UJacobi LJacobi UAIRG LAIRG Ulevel sets
qmd11224488558
nd22113466556
colamd33371658451159076123

Table 4. The effect of the unknown ordering on the ILU(0) factors of the advection-diffusion problem (7.3) with β=10000\beta= 10000, N=100N = 100, for the three orderings (out of the nine tested) for which the exact ILU(0)-preconditioned Ax = b solve converges.

The number of AIRG levels also varies with the ordering, rising from 5 under QMD and ND to 7 under COLAMD; the easiest factors coincide with the shallowest hierarchies. It is likewise well known that the parallelism available to an exact triangular solve depends strongly on the ordering (e.g., see [26, 11, 10] and the references therein), and the level-set counts here bear this out: a level-set substitution of these factors has 6 level sets under ND but 123 under COLAMD, compared with 7 AIRG levels. We also note that the parallelism available to a level-scheduled triangular solve degrades under refinement. With a natural ordering, the ILU(0) factors of this problem have 2N−12N - 1 level sets, growing from 199 at N=100N = 100 to 1599 at N=800N = 800, whereas, as discussed in § 5.4, the number of levels in a multigrid hierarchy grows only logarithmically.

Anisotropic diffusion

The anisotropic diffusion problem is

−ε∂2u∂x2−∂2u∂y2=fon Ω,(13)-\varepsilon\frac{\partial^2 u}{\partial x^2} - \frac{\partial^2 u}{\partial y^2} = f \quad\text{on } \Omega, \tag*{(13)}

where ε∈(0,1]\varepsilon\in(0,1] is the anisotropy ratio; yy is the strong direction and xx the weak direction. We use a second-order central-difference 5-point stencil, which gives a symmetric positive definite matrix, and we set ε=10−6\varepsilon= 10^{-6} to produce very anisotropic diffusion. We sweep the grid size N∈{100,200,450,800}N \in\{100,200,450,800\} at this fixed anisotropy ratio. Table 5 gives the number of iterations required to solve the L and U factors for the ILU(0) factorisation; the ILU(1) factorisation gives the same result, with every count within one of its ILU(0) value.

NNAIRGGMRES polyISAIJacobi
LULULULU
1002240395050100100
200227272100100200200
45022150149225225450450
80022256255400400800800

Table 5. For the anisotropic diffusion problem (7.5) with ε=10−6\varepsilon= 10^{-6} the number of iterations to solve the L and U factors generated by an ILU(0) factorisation to a relative tolerance of 10−610^{-6}, as the grid is refined (the winning ordering is natural at every NN). “MAX” denotes hitting the maximum iteration count (2000) and “DIV” indicates the solve diverged.

This problem shows the largest difference between the methods under refinement. For both the ILU(0) and ILU(1) factorisations, AIRG solves both factors in 2 iterations at every grid size, independent of NN. Every other method, by contrast, has an iteration count that grows with the grid size: linearly for Jacobi and ISAI, and slightly more slowly for the GMRES polynomials. For ILU(0), the Jacobi count on each factor grows from 100 at N=100N = 100 to 800 at N=800N = 800, ISAI from 50 to 400 and the GMRES polynomial from 40 to 256. The strong-direction coupling produces long dependency chains in the factors, exactly the structure that makes a single-level iterative solve scale poorly under refinement, whereas the AIRG hierarchy reduces these to a constant number of iterations.

SuiteSparse problems

We now test the iterative methods on 91 symmetric and nonsymmetric matrices drawn from the SuiteSparse Matrix Collection [18] and the Matrix Market [8]; they are listed, with their sizes and application areas, in Tables SM1 and SM2 of the supplementary materials. Many of these matrices were selected as they are tested in related papers, namely [11, 27, 3, 4, 5, 10]. For every one of these matrices, GMRES(30) preconditioned by the ILU factorisation with exact triangular solves does not diverge, although it converges within 2000 iterations on only 66 of them for ILU(0) and 71 for ILU(1). The L and U solves in § 6.4.1 are reported for all of the matrices, and the Ax = b timings in Section 7.4.2 for those that converge. The results in this section were run on LUMI-G (CSC, Finland). We used one MPI rank, which on the AMD MI250X GPUs of LUMI-G corresponds to using one Graphics Compute Die (GCD, of which there are two per AMD MI250X) with 64 GB of high-bandwidth memory available per GCD. Using one MPI rank allows us to make easy comparisons against an exact triangular solve, namely the hipSPARSE triangular solve available through PETSc (Section SM1 of the supplementary materials).

We configure PETSc with 64-bit indices in order to get timings representative of those at scale. For the iterative methods we use Kokkos Kernels SpMVs, rather than the hipSPARSE SpMVs; comparisons show the hipSPARSE SpMVs are typically faster on larger problems (up to 1.8×), but slower on smaller ones.

L and U factor solves

We begin by solving the LL and UU factors. The full per-matrix iteration counts for the symmetric and nonsymmetric matrices with ILU(0) and ILU(1) are given in Tables SM3 to SM6 of the supplementary materials.

For both the ILU(0) and ILU(1) factorisations, AIRG is very robust. We categorise failure as hitting the maximum number of iterations (2000), diverging on either of the LL or UU factors, or not finishing, either due to time (we allow a maximum time per matrix of 600 seconds) or memory limitations. For ILU(0), AIRG fails on only 3 of the 91 matrices. On CRANKSEG_1 (#73) and CRANKSEG_2 (#74) it did not finish, as the setup exceeded the time limit (a rerun of CRANKSEG_1 with a longer limit exhausted the host memory of the node), and it diverged on BCSSTK36 (#63). We note that all other iterative methods also fail on that problem. ISAI fails on the same number of matrices, diverging on 3, with GMRES polynomials failing on 11 and Jacobi the least robust, failing on 21. For ILU(1), three matrices did not finish with AIRG, with no outright failures: the setup exceeded the time limit on both CRANKSEG matrices and on the UU factor of S3RMQ4M1 (#41). ISAI diverged on three, with the GMRES polynomial failing on 12 and Jacobi failing on 22 of the test matrices.

For problems where both the LL and UU factors could be solved, we take the larger of the LL and UU iteration counts for each matrix. These are relatively low for AIRG with ILU(0), ranging from 1 to 9. The range is larger for ISAI at 1–68, and much larger for the GMRES polynomial at 1–1619, with Jacobi at 2–157. For ILU(1) the iteration counts are generally comparable, with AIRG at 1–10, ISAI at 1–79, GMRES polynomials at 1–365 and Jacobi at 2–144. The maximum iteration counts would suggest the GMRES polynomials are a poor method, but they are driven by two outliers, S2RMT3M1 (#36) for ILU(0) and BCSSTK17 (#49) for ILU(1). The median of these counts over the matrices on which each method succeeds is more reflective of the typical behaviour. For ILU(0) it is 3 for AIRG, 13 for ISAI, 5 for the GMRES polynomial and 26 for Jacobi, and for ILU(1) it is 3 for AIRG, 18 for ISAI, 8 for the GMRES polynomial and 37 for Jacobi.

The GMRES polynomials often succeed in relatively few iterations on problems where Jacobi diverges, such as GYRO_M (#48), WATHEN100 (#50), WATHEN120 (#54), PRES_POISSON (#61), CRANKSEG_1 (#73) and CRANKSEG_2 (#74) for ILU(0). The GMRES polynomials fail on more problems than ISAI, and largely on different ones: for both ILU(0) and ILU(1) the GMRES polynomial fails on 10 matrices on which ISAI succeeds, while it succeeds on two of the three matrices on which ISAI fails for ILU(0), AFT01 (#21) and ND3K (#66), and on ND3K for ILU(1).

The robustness of AIRG comes at a cost, namely the time required to set up the multigrid hierarchy and the memory required to store it. Both Jacobi and the GMRES polynomials require no additional storage, while the ISAI requires one extra matrix per factor, which in this work we restrict to the sparsity of the original factors. AIRG typically requires more storage for the multigrid hierarchy, but this is problem dependent.

We compute the grid and storage complexity of the AIRG hierarchies built on the LL and UU factors for each problem, taken as the maximum over the two factors.

For ILU(0) the grid complexity ranges from 1.05 on Chem97ZtZ (#3) to 26.93 on s3rmq4m1 (#41), with 62 of the 89 hierarchies below 3 (57 of the 88 for ILU(1)), reflecting how easily large diagonally dominant submatrices can be extracted in different problems (§ 5.3). The storage complexity ranges from 1.47 on Trefethen 20000 (#53) to 24.65 on cfd1 (#64) and exceeds 10 on 14 of the hierarchies (15 for ILU(1)), in particular for dense structural problems such as the cylindrical shell matrices. The ILU(1) ranges are 1.05–23.24 and 0.39–23.96, respectively; the storage complexity below one (again on Trefethen 20000) arises because only the operators needed for F-point smoothing are stored on each level (§ 6). The median complexities are more representative: for ILU(0) the median grid complexity is 2.51 and the median storage complexity 4.82, with ILU(1) similar at 2.66 and 6.22.

Before moving on to the solve time, we compare, for the L factor of each ILU(0) test matrix, the number of AIRG levels against the number of level sets (§ 5.4). AIRG builds fewer levels than there are level sets in all but one of the test matrices; the single exception is Chem97ZtZ (#3), where both have two.

The key observation is that the number of AIRG levels is more constant across the range of problems; AIRG builds a hierarchy of between 2 and 108 levels (a median of 5). The median number of levels of 5 here matches the level at which we start testing for auto-truncation. For many of the matrices tested, a GMRES polynomial can form a sufficiently good coarse-grid solver to allow such heavy truncation. Without auto-truncation the median number of levels is 13. It is also not just small matrices that benefit from heavy truncation. For example, af shell3 (#75) and CoupCons3D (#90) both require 19 multigrid levels without truncation, but the hierarchy can be truncated at 5 levels without affecting convergence. As noted above, truncating a multigrid hierarchy increases the amount of work required in the solve, as the coarsest matrix is larger, but given our coarse-grid solve is a GMRES polynomial this work is very parallel. We see this reflected in the solve times, which decrease with auto-truncation, with a median speedup of between 1.4×1.4\times and 1.5×1.5\times across the L and U factors at both fill levels.

For a level-set approach, the number of level sets has a median of 529 and reaches 20133 on Transport (#91), whose AIRG hierarchy has only 5 levels. In some problems the level-set approach is entirely serial, e.g., each of the 2000 level sets of the L factor of Trefethen-2000 (#11, n=2000n=2000) is a single row, against 5 AIRG levels. The ILU(1) factors show similar behaviour, made more pronounced by the additional fill, which lengthens the level-set dependency chains (a median of 828 level sets, compared with a median of 5 AIRG levels), and the same is true of the setup costs and Ax=bAx=b solve times discussed below. AIRG therefore requires far fewer sequential steps than an exact triangular solve, even on problems where the exact solve has low parallelism. The single-level methods (Jacobi, ISAI and the GMRES polynomials) have no level dependence at all, as each of their iterations consists of fully parallel SpMVs, so their number of sequential steps is set by their iteration count.

All methods except Jacobi, however, cost time to set up, including the exact triangular solve, whose level-set analysis phase must run before the first solve. Figure 2 compares the setup cost of the different methods for ILU(0), again taken as the maximum over the L and U factors (the ILU(1) counterpart is given in Section SM4 of the supplementary materials). The GMRES polynomial is the cheapest of the approximate methods to set up as it only requires generating the polynomial coefficients, whereas AIRG is the most expensive as it must build the multigrid hierarchy, with ISAI in between. The median setup cost for ILU(0) is 0.43 ms for the exact triangular solve, 3.7 ms for the GMRES polynomial, 9.7 ms for ISAI and 366 ms for AIRG, with the ILU(1) costs at 0.57 ms, 3.9 ms, 12.7 ms and 575 ms, respectively. The setup costs of AIRG also have a long tail: it takes more than 10 s on 5 of the problems for ILU(0), up to 54.5 s on S3RMQ4M1 (#41), and on 12 for ILU(1), up to 89.1 s on CoupCons3D (#90). ISAI exceeds 10 s only for ILU(1), on ND3K (#66, 97.5 s) and CRANKSEG_2 (#74), while the GMRES polynomial and the exact triangular solve never take more than 0.25 s. These setup times exclude the ILU factorisation itself and the ordering sweep of Section 2, which are the same for every method.

Setup time comparison plot

Figure 2. Setup time comparison (smaller is better) between the GMRES polynomial, ISAI, AIRG and the analysis phase of the hipSPARSE exact triangular solve for the L and U factors generated by the ILU(0) factorisation of each test matrix, ordered as in the results tables (symmetric and nonsymmetric matrices separated by the dashed line). The results shown are taken as the maximum over the L and U factors. Jacobi requires no setup and is not shown.

Solving Ax=b

We now move to solving the Ax = b system, using an outer GMRES(30) preconditioned by the ILU factorisation, with the inner application of L⁻¹ and U⁻¹ performed by iterative methods as detailed in the previous section. We use a random right-hand side and an initial guess of zero, and solve to a relative tolerance of 10⁻⁶, with a maximum number of outer iterations set to 2000. To ensure fair comparisons, we do not plot timing results for problems that diverged or reached the limit of 2000 outer iterations. The time of a solve that reaches the limit is just 2000 times the cost of one outer iteration; comparing such times would compare only the cost per iteration of each inner solve and ignore the number of iterations needed to converge, which Section 7.4.1 showed varies widely between methods and problems. As a baseline we show the timing results from using an exact inner triangular solve.

We know from [11, 3, 10] that a few iterations of an iterative method are sufficient in some problems to converge the inner solve well enough to not (overly) affect the outer iteration count. Choosing how many inner iterations to apply, however, is problem dependent; we could choose to solve each inner problem to a set tolerance but that would require computing a norm at each iteration (we would like to avoid dot products in the inner solve) and would require a flexible Krylov method for the outer solve (increasing the memory required). Instead, we choose a fixed number of iterations for the inner solve.

As AIRG solves either factor to a relative tolerance of 10⁻⁶ in a median of 3 iterations (and at most 10, Section 7.4.1), we use only a single V-cycle for both L and U on the inner solve. This gives the same median number of outer iterations as an exact triangular solve for both ILU(0) and ILU(1). Picking the best number of inner iterations for the Jacobi, ISAI and GMRES polynomial methods is more difficult, as their iteration counts when solving L or U to 10⁻⁶ vary from a handful to hundreds, as noted in § 6.4.1. To determine a fair number, we ran each test matrix for both fill levels with each of these methods using a fixed number of inner iterations from {1,2,3,5,8,13,21,34,55,89,144}\{1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144\}. For each problem and method we use the number of inner iterations that resulted in the smallest runtime while still converging. All the solve times reported in this section are from warmed-up runs, so one-time GPU initialisation costs (which can be comparable to the solve time of the smaller problems) are excluded.

Table 6 summarises the results, with the solve time for each test matrix given in Figure SM2 and Figure SM3 of the supplementary materials. AIRG is faster than the hipSPARSE exact triangular solve on only 32 of the 64 problems where both converge for ILU(0) and 41 of the 69 for ILU(1), with median speedups of 1.1× and 1.4×, respectively. The larger setup cost of AIRG is therefore not repaid quickly: on the problems where AIRG is faster, the extra setup time for both factors (relative to the analysis phase of the exact triangular solve) is recovered after a median of 28.4 solves of Ax=bAx = b for ILU(0) and 24.1 for ILU(1), and within 10 solves on only 9 of the 32 and 13 of the 41 such problems, respectively. The tuned Jacobi, ISAI and GMRES polynomial inner solves are faster than the exact triangular solve on all but 12, 6 and 9, respectively, of the problems where both converge for ILU(0), and 10, 7 and 9 for ILU(1).

ILU(0)ILU(1)
MethodConv.FastestAlln≥105n \ge10^{5}Conv.FastestAlln≥105n \ge10^{5}
Exact6651171511
AIRG6401.11.26921.42.3
Jacobi6342.62.26533.22.3
GMRES poly6763.02.471125.02.1
ISAI67524.52.770506.82.6

Table 6. Summary of the Ax=bAx = b solves on the 91 SuiteSparse/Matrix Market problems. “Conv.” is the number of problems solved, “Fastest” the number on which the method had the smallest solve time, and “Speedup” the median speedup over the exact triangular solve on the problems where both converged, over all of them and over those with n≥105n \ge10^{5}. Jacobi, ISAI and the GMRES polynomial use the best number of inner iterations for each problem.

Solve time comparison for the ILU(0) factorisation

Figure SM2. Solve time comparison (smaller is better) for the Ax=bA\mathbf{x}=\mathbf{b} solve with the ILU(0) factorisation for each test matrix, ordered as in the results tables (symmetric and nonsymmetric matrices separated by the dashed line). The solve uses an outer GMRES(30) preconditioned by the ILU factorisation, with the inner application of L−1L^{-1} and U−1U^{-1} performed by an exact triangular solve, by one V-cycle of AIRG, or by the Jacobi method, ISAI or the GMRES polynomial, each with the number of inner iterations that gave the smallest converged solve time for that problem. Only solves that converged to a relative tolerance of 10−610^{-6} are shown. Table 6 of the article summarises these results.

Solve time comparison for the ILU(1) factorisation

Figure SM3. Solve time comparison (smaller is better) for the Ax=bA\mathbf{x}=\mathbf{b} solve with the ILU(1) factorisation for each test matrix, ordered as in the results tables (symmetric and nonsymmetric matrices separated by the dashed line). The solve uses an outer GMRES(30) preconditioned by the ILU factorisation, with the inner application of L−1L^{-1} and U−1U^{-1} performed by an exact triangular solve, by one V-cycle of AIRG, or by the Jacobi method, ISAI or the GMRES polynomial, each with the number of inner iterations that gave the smallest converged solve time for that problem. Only solves that converged to a relative tolerance of 10−610^{-6} are shown. Table 6 of the article summarises these results.

Their speedups are also larger than those of AIRG, with ISAI the fastest: it is the fastest of all the methods on 52 of the problems for ILU(0) and 50 for ILU(1), with median speedups over the exact solve of 4.5× and 6.8×, respectively. Tuned in this way, ISAI and the GMRES polynomials also converge on slightly more problems than AIRG, while Jacobi converges on fewer. AIRG converges on every problem on which it finished, namely every problem on which the exact triangular solve converges except CRANKSEG_1 (#73) and CRANKSEG_2 (#74). ISAI and the GMRES polynomials converge on one more problem than the exact triangular solve with ILU(0), as does the GMRES polynomial with ILU(1): on AF_SHELL3 (#75) with ILU(0) and APACHE2 (#69) with ILU(1) the exact triangular solve stops just short of the tolerance at the limit of 2000 outer iterations, and the tuned methods converge there just inside the limit.

The difference between the methods, however, depends strongly on the problem size. The median speedup of AIRG over the exact triangular solve rises with the problem size, from 0.8×0.8 \times for the problems with n<20 000n < 20\,000 to 1.2×1.2 \times for those with n≥100 000n \ge100\,000 with ILU(0), and from 1.0×1.0 \times to 2.3×2.3 \times with ILU(1). The speedups of ISAI and the GMRES polynomials fall on the largest problems, most of all for ISAI, from 5.3×5.3 \times to 2.7×2.7 \times with ILU(0) and from 6.7×6.7 \times to 2.6×2.6 \times with ILU(1), while that of Jacobi changes little. Comparing ISAI directly with AIRG on the problems where both converge, ISAI is a median of 6.2×6.2 \times faster than AIRG for n<20 000n < 20\,000 but only 2.0×2.0 \times faster for n≥100 000n \ge100\,000 with ILU(0), and 5.8×5.8 \times and 1.5×1.5 \times faster with ILU(1); on the largest problems with ILU(1) all four iterative methods give similar median speedups, between 2.1×2.1 \times and 2.6×2.6 \times. The same trend holds when the problems are split by their nnz. This is consistent with the solves of the smaller problems being limited by the latency of launching GPU kernels rather than by the work they perform: an AIRG V-cycle launches several kernels on every level of the hierarchy, whereas the other methods apply only a few sparse matrix-vector products, and on the larger problems this fixed cost is amortised over more work.

These timings, however, rely on tuning the number of inner iterations of the simpler methods for each problem, which required solving each problem with 11 different inner iteration counts. The best number is not known in advance and varies widely between problems, as the factor solves in § 6.4.1 showed, and a poor choice can stop the outer solve from converging altogether.

Conclusions

In this paper we have compared four parallel iterative methods for solving the L\mathbf{L} and U\mathbf{U} triangular factors from ILU factorisations, namely a Jacobi method, ISAI, GMRES polynomials and the reduction multigrid AIRG, both on the factors alone and as the inner solve of an ILU preconditioner on a single GPU. All of the iterative methods compared in this work are available in the open-source PFLARE library, which can be installed directly through the PETSc configure with --download-pflare.

To improve the convergence of AIRG in difficult problems, we introduced the DIAG DOM CF splitting, which enforces a user-specified maximum diagonal dominance ratio on Aff\mathbf{A}_{\mathrm{ff}} with a single parameter, τ\tau, and is built entirely from parallel independent set routines, making it well suited to GPUs. AIRG requires far fewer sequential steps than an exact triangular solve: its hierarchies have a median of 5 levels on the tested problems, each requiring only a small number of fully parallel SpMVs, compared with a median of 529 level sets for an exact triangular solve of the ILU(0) factors (828 for ILU(1)), and on some matrices an exact substitution is essentially serial. The automatic truncation of the AIRG hierarchy we introduced previously further reduces the number of levels.

As the inner solve of an ILU preconditioner, the iterative methods gave only modest speedups over the hipSPARSE exact triangular solve. One V-cycle of AIRG was roughly break-even, with median speedups of 1.1×1.1 \times for ILU(0) and 1.4×1.4 \times for ILU(1), and where it was faster its larger setup cost took a median of 28.4 and 24.1 solves of Ax=b\mathbf{A}\mathbf{x} = \mathbf{b} to amortise, respectively. With the number of inner iterations tuned for each problem, the other methods were faster, with ISAI the fastest method on most problems and median speedups over the exact triangular solve of 4.5×4.5 \times for ILU(0) and 6.8×6.8 \times for ILU(1). This advantage comes mainly from the smaller problems, where kernel launch times can dominate: on the problems with n≥100 000n \ge100\,000 the speedups of the four methods are closer. For example, for ILU(1), all four iterative methods produced median speedups of between 2.1×2.1 \times and 2.6×2.6 \times compared with the exact triangular solve.

We note that these comparisons are on a single GPU; exact triangular solves often perform poorly with distributed-memory parallelism, which is why distributed ILU preconditioners commonly fall back to block Jacobi with local factors. In contrast, all four iterative methods tested in this work extend directly to distributed-memory parallelism (with GPU-aware MPI used in the setup and solve phases in PFLARE). In particular, AIRG has been shown to weak scale well up to 11k GPUs when solving triangular systems from discretisations of advection problems [17].

Overall, this work shows that each method has advantages and can provide speedups when compared to exact triangular solves. The Jacobi method is the simplest, with no setup and no additional storage, but is the least robust, failing on the most problems both when solving the factors and as an inner solve. The GMRES polynomials share these advantages but are more robust: they fail on roughly half as many problems when solving the factors, and as an inner solve they converge on every problem on which the Jacobi method converges (and on several more) with a similar or faster solve time, making them a potential replacement for a Jacobi method. ISAI gives the largest speedups as an inner solve and is as robust as AIRG on the SuiteSparse/Matrix Market factors, at the cost of one extra stored matrix per factor and a larger setup than the Jacobi method or GMRES polynomials, although it diverges on most of the ILU(1) advection-diffusion problems. AIRG is the most robust method when solving the factors, with nearly flat iteration counts under refinement where those of every other method grow or diverge, and needs no per-problem tuning. Its drawbacks are memory use, at a median of five to six copies of the factor, and the largest setup times. Which method is best therefore depends on whether robustness, solve time or memory use matters most, and on whether the inner solve is tuned for the problems of interest.

Acknowledgments. We acknowledge the EuroHPC Joint Undertaking for awarding this project access to the EuroHPC supercomputer LUMI, hosted by CSC (Finland) and the LUMI consortium through a EuroHPC Benchmark Access call.

Solver parameters

The factor solves described at the start of § 6 of the article use the following command-line options with PETSc:

-ksp_type richardson -ksp_norm_type unpreconditioned -ksp_rtol 1e-6 -ksp_atol
1e-50 -ksp_max_it 2000

When used as the inner solve of the ILU preconditioner for Ax=b\mathbf{A}\mathbf{x}=\mathbf{b} (§ 6.4.2 of the article), each factor is instead solved with a fixed number of iterations kk and without computing any norms or dot products: for k=1k=1 (and always for the single V-cycle of AIRG) we use

-ksp_type preonly

and for k>1k>1

-ksp_type richardson -ksp_norm_type none -ksp_max_it k

so that each inner solve is a fixed linear operator. The outer solve uses

-ksp_type gmres -ksp_gmres_restart 30 -ksp_norm_type unpreconditioned
-ksp_rtol 1e-6 -ksp_atol 1e-50 -ksp_max_it 2000

and the exact triangular solve baseline uses PETSc’s ILU factorisation (inside block Jacobi with one block, as we use one MPI rank), with the matrix converted to PETSc’s hipSPARSE format so that the triangular solves use hipSPARSE:

-mat_type aijhipsparse -vec_type hip -pc_type bjacobi -sub_pc_type ilu
-sub_pc_factor_mat_solver_type hipsparse

with -sub_pc_factor_levels 1 for ILU(1).

When using PFLARE we specify the matrix/vector types as the AIJKOKKOS format, since this ensures all the components of the setup and solve are run on the GPU. For AIRG we then also use:

-pc_type air -pc_air_cf_splitting_type diag_dom -pc_air_strong_threshold 0.5
-pc_air_a_drop 1e-6 -pc_air_r_drop 1e-4 -pc_air_diag_scale_polys
-pc_air_coarsest_diag_scale_polys -pc_air_coarsest_inverse_type newton
-pc_air_coarsest_poly_order 10 -pc_air_coarsest_matrix_free_polys
-pc_air_auto_truncate_start_level 5 -pc_air_auto_truncate_tol 1e-3

which uses the default 6th6^{\mathrm{th}}-order GMRES polynomial (m=7m=7) on all levels except the coarsest. With the DIAG-DOM CF splitting, -pc_air_strong_threshold sets both the strength threshold θ\theta and the maximum diagonal dominance ratio τ\tau of Algorithm 6.1 of the article (θ=τ\theta=\tau); the value τ=0.5\tau=0.5 used throughout is also the default. The last six options concern the coarse grid. Rather than coarsening until the problem is small enough to solve directly, from the fifth level onwards we test whether the coarse-grid solver alone can solve the current coarse problem to a relative tolerance of 10−310^{-3}, and if so we truncate the hierarchy there. The coarse-grid solver is a 10th10^{\mathrm{th}}-order GMRES polynomial in a Newton basis applied matrix-free, so it requires only matrix-vector products. This trades a higher cycle complexity for fewer levels, which is beneficial on GPUs where the lower levels of the hierarchy have little work but still incur kernel-launch costs.

The GMRES polynomial approximate inverse uses: -pc_type pflareinv -pc_pflareinv_type newton -pc_pflareinv_matrix_free

again with the default 6th6^{\mathrm{th}}-order polynomial, with coefficients computed in a Newton basis and applied matrix-free. The ISAI approximate inverse uses:

-pc_type pflareinv -pc_pflareinv_type isai

which defaults to using the sparsity pattern of the input matrix. The Jacobi iteration uses:

-pc_type jacobi

When solving Ax=b\mathbf{A}\mathbf{x}=\mathbf{b} with an ILU preconditioner whose triangular factors are applied approximately (Section 7.4.2), the factor solves above are instead applied as a fixed amount of work rather than to a tolerance, e.g., a single AIRG V-cycle or a fixed number of Jacobi iterations on the L\mathbf{L} and U\mathbf{U} factors.

Test matrices

SM2. Test matrices. Tables SM1 and SM2 list the 91 SuiteSparse/Matrix Market test matrices used in Section 7.4 of the article, in the order used in the article’s figures and in the results tables below (the symmetric matrices are numbered 1 to 76 and the nonsymmetric matrices 77 to 91, each group sorted by the number of nonzeros), with the size nn and number of nonzeros (nnz) of the full matrix and the application area recorded by the collections.

Table SM2

The nonsymmetric SuiteSparse/Matrix Market test matrices (numbers 77 to 91), with the size nn and number of nonzeros (nnz) of the full matrix and the application area recorded by the collections. The numbering is that used throughout the article.

Full results

SM3. Full results. Tables SM3 to SM6 give the per-matrix iteration counts for the L and U factor solves discussed in § 6.4.1 of the article, for the symmetric and nonsymmetric matrices with ILU(0) and ILU(1) factorisations. The solver parameters are those of Section SM1.

The ordering column of each table gives the winning ordering selected by the sweep described in § 1 of the article. The orderings swept are NATURAL, ND, RCM, QMD, 1WD and ROWLENGTH from PETSc, and COLAMD, MMD_ATA and MMD_AT_PLUS_A from SciPy. The last three are computed from the column structure (of AA, ATAA^{\mathsf{T}}A and AT+AA^{\mathsf{T}} + A, respectively), and SciPy exposes them only through its SuperLU interface, which returns a row permutation alongside the column ordering, chosen by its own threshold partial pivoting. We therefore extract these orderings from a probe factorisation with pivoting disabled (a diagonal pivot threshold of zero, so that the diagonal entry is always accepted as the pivot), in which case the row and column permutations returned coincide and the reordering is symmetric, PAPTPAP^{\mathsf{T}}.

#MatrixorderingAIRG LAIRG UGMRES poly LGMRES poly UISAI LISAI UJacobi LJacobi U
11138_busmmd_ata222255910
2bcsstk19natural54MAXMAX6368155157
3Chem97ZtZnatural11111122
4bcsstk081wd23412771716
5mhd3200brcm6645892122
6bcsstm12nd341118553334
7bcsstk10rcm4494402929DIVDIV
8mhd4800brcm6647992223
9msc01050natural337611219882424
10plbucklenatural35167815154142
11Trefethen_2000natural22123468
12bcsstk27natural3322192020DIVDIV
13bcsstk14rowlength2333771616
14nasa2146natural33171420206260
15fv1natural223310102222
16fv2natural223310102222
17msc04515nd35MAXMAX2018DIVDIV
18crystm01natural3355993636
19bcsstk15colamd3377892019
20bodyy4natural329713152630
#MatrixorderingAIRG LAIRG UGMRES poly LGMRES poly UISAI LISAI UJacobi LJacobi U
21aft01rcm442325108DIVDIVDIV
22bodyy5natural22201115183037
23bodyy6natural32331419213841
24ted_Bnatural3233551718
25ted_B_unscalednatural3233551718
26bcsstk18natural3362011122524
27bcsstk24rcm55MAXMAX1917DIV107
28Muurcm3333661919
29t2dah_ercm45555258DIVDIV
30obstclaenatural224412122323
31torsion1natural224412122323
32jnlbrng1natural227719193737
33minsurfonatural334412122424
34s3rmt3m3rcm97MAXDIV3330DIVDIV
35s1rmt3m1natural44172418187474
36s2rmt3m1natural5416195119188786
37s3rmt3m1natural69MAXMAX1717DIVDIV
38Dubcova1rcm337716164949
39s1rmq4m1natural44356420218386
40s2rmq4m1natural65MAX7720207571
41s3rmq4m1natural99DIVDIV2020DIVDIV
42chipcool01wd334413122928
43bcsstk16natural336718194139
44crystm02natural3355994747
45shallow_water1natural22225599
46shallow_water2rcm2233991717
47Kuurowlength3333651615
48gyro_m1wd43773332DIVDIV
49bcsstk17nd331098610959DIV
50wathen100natural44444445DIVDIV
51gridgenarcm336615154239
52apache1rcm23349101820
53Trefethen_20000colamd21113366
54wathen120natural44444545DIVDIV
55thermal1rcm335514143131
56crystm03natural3355995252
57finan512natural22224488
58cbuckleqmd347714188DIVDIV
59thermomech_TCrcm2222881819
60thermomech_TKrcm335515153232
61Pres_Poissonrcm4418112019DIVDIV
62bundle1qmd222233109
63bcsstk361wdDIVDIVDIVMAXDIVDIVDIVDIV
64cfd11wd5531315656DIVDIV
65bcsstk39mmd_ata56MAXMAX3131DIVDIV
66nd3knatural44265217DIVDIVDIVDIV
67parabolic_femrcm338822224646
68offshore1wd335413113026
69apache2natural224412122424
70ecology2rcm335513132626
71G3_circuitnatural3310931296257
72thermal21wd334413132929
73crankseg_1rcm3DNF21192219DIVDIV
74crankseg_2rcmDNFDNF24222522DIVDIV
75af_shell3rcm338826266868
76StocF-1465rcm42MAX2135337368

Table SM3. For the symmetric matrices from the SuiteSparse collection and Matrix Market (Table SM1) the number of iterations to solve the L and U factors generated by an ILU(0) factorisation to a relative tolerance of 10−610^{-6}. “MAX” denotes hitting the maximum iteration count (2000), “DIV” indicates the solve diverged and “DNF” indicates the method did not finish, either running out of memory or exceeding the time limit.

#MatrixnnnnzApplication area
11138_bus1 1384 054Power-system network
2bcsstk198176 853Structural (part of a suspension bridge)
3Chem97ZtZ2 5417 361Statistics (normal equations)
4bcsstk081 07412 960Structural (TV studio)
5mhd3200b3 20018 316Magnetohydrodynamics
6bcsstm121 47319 659Structural (mass matrix)
7bcsstk101 08622 070Structural mechanics (buckling)
8mhd4800b4 80027 520Magnetohydrodynamics
9msc010501 05029 156Structural mechanics
10plbuckle1 28230 644Structural (buckling plate)
11Trefethen_20002 00041 906Combinatorics (Trefethen)
12bcsstk271 22456 126Structural (buckling)
13bcsstk141 80663 454Structural (roof of Omni Coliseum)
14nasa21462 14672 250Structural mechanics
15fv19 60485 2642D finite-volume mesh
16fv29 80187 0252D finite-volume mesh
17msc045154 51597 707Structural mechanics
18crystm014 875105 339Materials (crystal mass matrix)
19bcsstk153 948117 816Structural (module of an offshore platform)
20bodyy417 546121 938Structural (FE mesh)
21aft018 205125 567Acoustics (vibroacoustics)
22bodyy518 589129 281Structural (FE mesh)
23bodyy619 366134 748Structural (FE mesh)
24ted_B10 605144 579Thermal model reduction
25ted_B_unscaled10 605144 579Thermal model reduction (unscaled)
26bcsstk1811 948149 090Structural (R.E. Ginna nuclear power station)
27bcsstk243 562159 910Structural (Calgary Olympic Saddledome arena)
28Muul7 102170 134Structural (FEM mass matrix)
#MatrixnnnnzApplication area
29t2dah_e11 445176 117Model reduction (micropyros thruster)
30obstclae40 000197 608Obstacle problem (optimisation)
31torsion140 000197 608Torsion (optimisation)
32jnlbrng140 000199 200Journal-bearing (optimisation)
33minsurfo40 806203 622Minimal-surface (optimisation)
34s3rmt3m35 357207 695Structural (cylindrical shell)
35s1rmt3m15 489219 521Structural (cylindrical shell)
36s2rmt3m15 489219 521Structural (cylindrical shell)
37s3rmt3m15 489219 521Structural (cylindrical shell)
38Dubcova116 129253 0092D/3D PDE
39s1rmq4m15 489281 111Structural (cylindrical shell)
40s2rmq4m15 489281 111Structural (cylindrical shell)
41s3rmq4m15 489281 111Structural (cylindrical shell)
42chipcool020 082281 150Thermal model reduction
43bcsstk164 884290 378Structural (Corps of Engineers dam)
44crystm0213 965322 905Materials (crystal mass matrix)
45shallow-water181 920327 680Climate (shallow-water)
46shallow-water281 920327 680Climate (shallow-water)
47Kuu7 102340 200Structural (FEM stiffness)
48gyro_m17 361340 431Model reduction (gyroscope mass matrix)
49bcsstk1710 974428 650Structural (elevated pressure vessel)
50wathen10030 401471 601Structural (Wathen FE)
51gridgena48 962512 084Optimisation (grid generation)
52apache180 800542 1843D structural mechanics
53Trefethen_2000020 000554 466Combinatorics (Trefethen)
54wathen12036 441565 761Structural (Wathen FE)
55thermal182 654574 458Steady-state thermal
56crystm0324 696583 770Materials (crystal mass matrix)
57finan51274 752596 992Financial portfolio optimisation
58cbuckle13 681676 515Structural (buckling)
59thermomech_TC102 158711 558Thermomechanical
60thermomech_TK102 158711 558Thermomechanical
61Pres_Poisson14 822715 804CFD (pressure Poisson)
62bundle110 581770 901Computer vision (bundle adjustment)
63bcsstk3623 0521 143 140Structural (automobile shock absorber)
64cfd170 6561 828 364CFD pressure matrix
65bcsstk3946 7722 089 294Structural (solid element model)
66nd3k9 0003 279 6903D mesh problem (ND set)
67parabolic_fem525 8253 674 625Parabolic FEM, convection-diffusion
68offshore259 7894 242 673Electromagnetics (offshore EM survey)
69apache2715 1764 817 8703D structural mechanics
70ecology2999 9994 995 9912D circular food-web model
71G3_circuit1 585 4787 660 826Circuit simulation
72thermal21 228 0458 580 313Steady-state thermal
73crankseg_152 80410 614 210Structural (crank segment)
74crankseg_263 83814 148 858Structural (crank segment)
75af_shell3504 85517 588 875Structural (sheet-metal forming)
76StocF-14651 465 13721 005 389Fluid flow (stochastic FEM)

Table SM1. The symmetric SuiteSparse/Matrix Market test matrices (numbers 1 to 76), with the size nn and number of nonzeros (nnz) of the full matrix and the application area recorded by the collections. The numbering is that used throughout the article.

#MatrixorderingAIRG LAIRG UGMRES poly LGMRES poly UISAI LISAI UJacobi LJacobi U
11138_busrcm32238717163732
2bcsstk19rcm44MAXMAX4545DIVDIV
3Chem97ZtZnatural11111122
4bcsstk08rcm33521771617
5mhd3200bnatural6656891922
6bcsstm12nd231117443334
7bcsstk101wd331226662828
8mhd4800bnatural6657992022
9msc01050qmd23810783132
10plbucklenatural45102116164346
11Trefethen_2000nd22113366
12bcsstk27natural4436232121DIVDIV
13bcsstk14rcm33112116164550
14nasa2146natural33181417176159
15fv1natural224411112626
16fv2natural224411112626
17msc04515rcm54138462826DIVDIV
18crystm01natural3355663636
19bcsstk15rcm44442014143638
20bodyy4natural339713152630
21aft01natural6329307879DIVDIV
22bodyy5natural32201115183036
23bodyy6natural32331419213841
24ted_Bnatural3233551718
25ted_B_unscalednatural3233551718
26bcsstk18mmd_at_plus_a33957871917
27bcsstk24rcm65MAXMAX2726DIVDIV
28Muurcm3333661919
29t2dah_enatural34337795144
30obstclaenatural336617173535
31torsion1natural336617173535
32jnlbrng1natural33121233336666
33minsurfonatural336618183737
34s3rmt3m3rcm98MAXDIV3632DIVDIV
35s1rmt3m1rcm44803032319190
36s2rmt3m1natural44MAX17123219392
37s3rmt3m1natural810MAXDIV2220DIVDIV
38Dubcova1rcm339922205150
39s1rmq4m1natural44848922228283
40s2rmq4m1natural66MAX1702322106102
41s3rmq4m1natural9DNFMAXDIV2423DIVDIV
42chipcool0natural337720205050
43bcsstk16natural339922235353
44crystm02natural3355664747
45shallow_water1rcm2222661111
46shallow_water2rcm233310101919
47Kuu1wd33171722239692
48gyro_mnatural3313112120DIVDIV
49bcsstk17rowlength34365761514DIVDIV
50wathen100natural44442121DIVDIV
51gridgenaqmd2233891921
52apache1rcm334513142730

Table SM4. For the symmetric matrices from the SuiteSparse collection and Matrix Market (Table SM1) the number of iterations to solve the L and U factors generated by an ILU(1) factorisation to a relative tolerance of 10−610^{-6}. “MAX” denotes hitting the maximum iteration count (2000), “DIV” indicates the solve diverged and “DNF” indicates the method did not finish, either running out of memory or exceeding the time limit.

#MatrixorderingAIRG LAIRG UGMRES poly LGMRES poly UISAI LISAI UJacobi LJacobi U
53Trefethen_20000natural22123468
54wathen120natural44442121DIVDIV
55thermal11wd337619194444
56crystm03natural3355665252
57finan512natural22224488
58cbucklercm44794MAX2223DIVDIV
59thermomech_TCrcm2222771717
60thermomech_TKrcm337722225049
61Pres_Poissonrcm5320142625DIVDIV
62bundle1rowlength2222331212
63bcsstk36rcm89DIVDIVDIVDIVDIVDIV
64cfd11wd5549515354DIVDIV
65bcsstk39nd45MAXMAXDIVDIVDIVDIV
66nd3knatural3313395DIVDIVDIVDIV
67parabolic_femrcm43111131316666
68offshorenatural444064282983DIV
69apache2natural336618193840
70ecology2natural338822224646
71G3_circuitnatural4310932306359
72thermal2rcm337721214948
73crankseg_1rcmDNFDNF22201918DIVDIV
74crankseg_2rcmDNFDNF26232119DIVDIV
75af_shell3rcm33101032329694
76StocF-1465rcm53MAX2341379480

Table SM5. Table SM5. For the nonsymmetric matrices from the SuiteSparse collection and Matrix Market (Table SM2) the number of iterations to solve the L and U factors generated by an ILU(0) factorisation to a relative tolerance of 10−610^{-6}. “MAX” denotes hitting the maximum iteration count (2000), “DIV” indicates the solve diverged and “DNF” indicates the method did not finish, either running out of memory or exceeding the time limit.

#MatrixnnnnzApplication area
77cage1011 397150 645DNA electrophoresis
78cage1139 082559 722DNA electrophoresis
79ASIC_100ks99 190578 890Circuit simulation
80trans4116 835766 396Circuit simulation
#MatrixnnnnzApplication area
81torso2115 9671 033 473Bioengineering (electrocardiology)
823D_51448_3D51 4481 056 610Structural (3D problem)
83venkat0162 4241 717 792CFD (unstructured 2D Euler)
84majorbasis160 0001 750 416Optimisation
85poisson3Db85 6232 374 949CFD (3D Poisson)
86stomach213 3603 021 648Bioengineering (3D EM model of duodenum)
87tmt_unsym917 8254 584 801Electromagnetics
88atmosmodd1 270 4328 814 880Atmospheric modelling
89Freescale13 428 75518 920 347Circuit simulation
90CoupCons3D416 80022 322 336Structural (coupled consolidation)
91Transport1 602 11123 500 731Structural (3D transport)

Table SM2.

#MatrixorderingAIRG LAIRG UGMRES poly LGMRES poly UISAI LISAI UJacobi LJacobi U
77cage10natural2222551011
78cage11natural2222551011
79ASIC_100ksrcm221502951811
80trans4rcm22123478
81torso2natural2233771616
823D_51448_3Drowlength53MAX616165732
83venkat01rcm54111429335982
84majorbasisrcm336516133927
85poisson3Db1wd2343992321
86stomachrcm335514142728
87tmt_unsymrcm335513132626
88atmosmoddrcm224413122524
89Freescale1natural22111133326663
90CoupCons3Dnatural346717183741
91Transportrcm337721214444

Table SM5 (PDF p. 31).

#MatrixorderingAIRG LAIRG UGMRES poly LGMRES poly UISAI LISAI UJacobi LJacobi U
77cage10natural22224599
78cage11natural22224599
79ASIC_100ksnatural221962851510
80trans4rcm2222441313
81torso2rcm2233771717
823D_51448_3Dnatural54MAX102421DIV44
83venkat01rcm54131634367089
84majorbasisrcm337516154230
85poisson3Dbnatural2233661919
86stomachrcm335513143029
87tmt_unsymrcm338822224646
88atmosmoddrcm337721204242
89Freescale1natural22141443418681
90CoupCons3Dnatural347818203538
91Transportrcm33111130306464

Table SM6. For the nonsymmetric matrices from the SuiteSparse collection and Matrix Market (Table SM2) the number of iterations to solve the L and U factors generated by an ILU(1) factorisation to a relative tolerance of 10−610^{-6}. “MAX” denotes hitting the maximum iteration count (2000), “DIV” indicates the solve diverged and “DNF” indicates the method did not finish, either running out of memory or exceeding the time limit.

Setup and solve time figures

Figure SM1 is the ILU(1) counterpart of Figure 2 of the article (which shows the ILU(0) factorisation), discussed in Section 7.4.1 of the article. Figures SM2 and SM3 give the Ax=bAx=b solve time for each test matrix, summarised in Table 6 and discussed in Section 7.4.2 of the article.

Setup time comparison between the GMRES polynomial, ISAI, AIRG and the analysis phase of the hipSPARSE exact triangular solve

Figure SM1. Setup time comparison (smaller is better) between the GMRES polynomial, ISAI, AIRG and the analysis phase of the hipSPARSE exact triangular solve for the L and U factors generated by the ILU(1) factorisation of each test matrix, ordered as in the results tables (symmetric and nonsymmetric matrices separated by the dashed line). The results shown are taken as the maximum over the L and U factors. Jacobi requires no setup and is not shown. The ILU(0) factors are shown in Figure 2 of the article.

References

  1. [1]A. Ali, J. J. Brannick, K. Kahl, O. A. Krzyzik, J. B. Schroder, and B. S. Southworth, Constrained Local Approximate Ideal Restriction for Advection-Diffusion Problems, SIAM Journal on Scientific Computing, 46 (2024), pp. S96–S122.DOI
  2. [2]F. L. Alvarado and R. Schreiber, Optimal Parallel Solution of Sparse Triangular Systems, SIAM Journal on Scientific Computing, 14 (1993), pp. 446–460.DOI
  3. [3]H. Anzt, E. Chow, and J. Dongarra, Iterative Sparse Triangular Solves for Preconditioning, in Euro-Par 2015: Parallel Processing, J. L. Träff, S. Hunold, and F. Versaci, eds., vol. 9233 of Lecture Notes in Computer Science, Berlin, Heidelberg, 2015, Springer, pp. 650–661.DOI
  4. [4]H. Anzt, E. Chow, and J. Dongarra, ParILUT—A New Parallel Threshold ILU Factorization, SIAM Journal on Scientific Computing, 40 (2018), pp. C503–C519.DOI
  5. [5]H. Anzt, T. K. Huckle, J. Bräckle, and J. Dongarra, Incomplete Sparse Approximate Inverses for Parallel Preconditioning, Parallel Computing, 71 (2018), pp. 1–22.DOI
  6. [6]S. Balay, S. Abhyankar, M. F. Adams, S. Benson, J. Brown, P. Brune, K. Buschelman, E. M. Constantinescu, L. Dalcin, A. D. Dana, J. Dener, V. Eijkhout, J. Faibussowitsch, W. D. Gropp, V. Hapla, T. Isaac, P. Jolivet, D. Karpeev, D. Kaushik, M. G. Knepley, F. Kong, S. Kruger, D. A. May, L. C. McInnes, R. T. Mills, L. Mitchell, T. Munson, J. E. Roman, K. Rupp, P. Sanan, J. Sarch, B. F. Smith, S. Zampini, H. Zhang, H. Zhang, and J. Zhang, PETSc Web page. https://petsc.org/, 2026.
  7. [7]M. Benzi, D. B. Szyld, and A. Van Duin, Orderings for Incomplete Factorization Preconditioning of Nonsymmetric Problems, SIAM Journal on Scientific Computing, 20 (1999), pp. 1652–1670.
  8. [8]R. F. Boisvert, R. Pozo, K. Remington, R. F. Barrett, and J. J. Dongarra, Matrix Market: a web resource for test matrix collections, in Quality of Numerical Software: Assessment and Enhancement, R. F. Boisvert, ed., Springer US, Boston, MA, 1997, pp. 125–137.
  9. [9]E. Chow, A Priori Sparsity Patterns for Parallel Sparse Approximate Inverse Preconditioners, SIAM Journal on Scientific Computing, 21 (2000), pp. 1804–1822.DOI
  10. [10]E. Chow, H. Anzt, J. Scott, and J. Dongarra, Using Jacobi iterations and blocking for solving sparse triangular systems in incomplete factorization preconditioning, Journal of Parallel and Distributed Computing, 119 (2018), pp. 219–230.DOI
  11. [11]E. Chow and A. Patel, Fine-Grained Parallel Incomplete LU Factorization, SIAM Journal on Scientific Computing, 37 (2015), pp. C169–C193.DOI
  12. [12]E. Chow and Y. Saad, Experimental study of ILU preconditioners for indefinite matrices, Journal of Computational and Applied Mathematics, 86 (1997), pp. 387–414.DOI
  13. [13]E. Chow and Y. Saad, Approximate Inverse Preconditioners via Sparse-Sparse Iterations, SIAM Journal on Scientific Computing, 19 (1998), pp. 995–1023.DOI
  14. [14]S. Dargaville, R. P. Smedley-Stevenson, P. N. Smith, and C. C. Pain, AIR multigrid with GMRES polynomials (AIRG) and additive preconditioners for Boltzmann transport, Journal of Computational Physics, 518 (2024), p. 113342.arxiv.org/abs/2301.05521
  15. [15]S. Dargaville, R. P. Smedley-Stevenson, P. N. Smith, and C. C. Pain, Angular Adaptivity in P0 Space and Reduced Tolerance Solves for Boltzmann Transport, Nuclear Science and Engineering, 198 (2024), pp. 1235–1254.arxiv.org/abs/2301.06579
  16. [16]S. Dargaville, R. P. Smedley-Stevenson, P. N. Smith, and C. C. Pain, Coarsening and parallelism with reduction multigrids for hyperbolic Boltzmann transport, The International Journal of High Performance Computing Applications, 39 (2025), pp. 364–384.arxiv.org/abs/2408.08262
  17. [17]S. Dargaville, R. P. Smedley-Stevenson, P. N. Smith, and C. C. Pain, Solving advection equations with reduction multigrids on GPUs, Journal of Computational Physics, 565 (2026), p. 115177.arxiv.org/abs/2508.17517
  18. [18]T. A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Transactions on Mathematical Software (TOMS), 38 (2011), pp. 1:1–1:25.DOI
  19. [19]H. De Sterck, U. M. Yang, and J. J. Heys, Reducing complexity in parallel algebraic multigrid preconditioners, SIAM Journal on Matrix Analysis and Applications, 27 (2006), pp. 1019–1039.DOI
  20. [20]M. Embree, J. A. Henningsen, J. Jackson, and R. B. Morgan, Polynomial approximation to the inverse of a large matrix, SIAM Journal on Scientific Computing, 48 (2026), pp. S258–S284.
  21. [21]R. D. Falgout, R. Li, B. Sjögreen, L. Wang, and U. M. Yang, Porting hypre to heterogeneous computer architectures: Strategies and experiences, Parallel Computing, 108 (2021), p. 102840.DOI
  22. [22]G. H. Golub and R. S. Tuminaro, Cyclic reduction/multigrid, Tech. Report NA-92-14, Numerical Analysis Project, Computer Science Department, Stanford University, 1992, http://infolab.stanford.edu/pub/cstr/reports/na/m/92/14/NA-M-92-14.pdf.
  23. [23]M. J. Grote and T. Huckle, Parallel Preconditioning with Sparse Approximate Inverses, SIAM Journal on Scientific Computing, 18 (1997), pp. 838–853.
  24. [24]N. J. Higham and A. Pothen, Stability of the Partitioned Inverse Method for Parallel Solution of Sparse Triangular Systems, SIAM Journal on Scientific Computing, 15 (1994), pp. 139–148.DOI
  25. [25]L. Y. Kolotilina and A. Y. Yeremin, Factorized Sparse Approximate Inverse Preconditionings I. Theory, SIAM Journal on Matrix Analysis and Applications, 14 (1993), pp. 45–58.DOI
  26. [26]J. W. H. Liu, The Role of Elimination Trees in Sparse Factorization, SIAM Journal on Matrix Analysis and Applications, 11 (1990), pp. 134–172.DOI
  27. [27]W. Liu, A. Li, J. Hogg, I. S. Duff, and J. Vinter, A Synchronization-Free Algorithm for Parallel Sparse Triangular Solves, in Euro-Par 2016: Parallel Processing, P.-F. Dutot and D. Trystram, eds., vol. 9833 of Lecture Notes in Computer Science, Cham, 2016, Springer, pp. 617–630.DOI
  28. [28]J. A. Loe and R. B. Morgan, Toward efficient polynomial preconditioning for GMRES, Numerical Linear Algebra with Applications, 29 (2022), p. e2427.DOI
  29. [29]Z. Lu, A sparse approximate inverse for triangular matrices based on Jacobi iteration, 2021, https://arxiv.org/abs/2106.12836.
  30. [30]Z. Lu, Y. Ni, and W. Liu, Efficient Block Algorithms for Parallel Sparse Triangular Solve, in Proceedings of the 49th International Conference on Parallel Processing, ICPP ’20, New York, NY, USA, Aug. 2020, Association for Computing Machinery, pp. 1–11.DOI
  31. [31]S. MacLachlan and Y. Saad, Greedy Coarsening Strategies for Nonsymmetric Problems, SIAM Journal on Scientific Computing, 29 (2007), pp. 2115–2143.DOI
  32. [32]S. MacLachlan and Y. Saad, A Greedy Strategy for Coarse-Grid Selection, SIAM Journal on Scientific Computing, 29 (2007), pp. 1825–1853.DOI
  33. [33]T. Manteuffel and B. S. Southworth, Convergence in Norm of Nonsymmetric Algebraic Multigrid, SIAM Journal on Scientific Computing, 41 (2019), pp. S269–S296.
  34. [34]T. A. Manteuffel, S. Münzenmaier, J. Ruge, and B. Southworth, Nonsymmetric Reduction-Based Algebraic Multigrid, SIAM Journal on Scientific Computing, 41 (2019), pp. S242–S268.arxiv.org/abs/1704.05001
  35. [35]T. A. Manteuffel, J. Ruge, and B. S. Southworth, Nonsymmetric algebraic multigrid based on local approximate ideal restriction (ℒAIR), SIAM Journal on Scientific Computing, 40 (2018), pp. A4105–A4130.arxiv.org/abs/1708.06065
  36. [36]N. M. Nachtigal, L. Reichel, and L. N. Trefethen, A hybrid GMRES algorithm for nonsymmetric linear systems, SIAM Journal on Matrix Analysis and Applications, 13 (1992), pp. 796–825.DOI
  37. [37]M. Naumov, Parallel Solution of Sparse Triangular Linear Systems in the Preconditioned Iterative Methods on the GPU, NVIDIA Technical Report NVR-2011-001, NVIDIA, June 2011, https://research.nvidia.com/publication/2011-06_parallel-solution-sparse-triangular-linear-systems-preconditioned-iterative.
  38. [38]M. Naumov, M. Arsaev, P. Castonguay, J. Cohen, J. Demouth, J. Eaton, S. Layton, N. Markovskiy, I. Reguly, N. Sakharov, V. Sellappan, and R. Strodzka, AmgX: A Library for GPU Accelerated Algebraic Multigrid and Preconditioned Iterative Methods, SIAM Journal on Scientific Computing, 37 (2015), pp. S602–S626.DOI
  39. [39]S. Rajamanickam, S. Acer, L. Berger-Vergiat, V. Dang, N. Ellingwood, E. Harvey, B. Kelley, C. R. Trott, J. Wilke, and I. Yamazaki, Kokkos Kernels: Performance portable sparse/dense linear algebra and graph kernels, 2021, https://arxiv.org/abs/2103.11991.
  40. [40]Y. Saad, ILUM: A Multi-Elimination ILU Preconditioner for General Sparse Matrices, SIAM Journal on Scientific Computing, 17 (1996), pp. 830–847.DOI
  41. [41]Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, 2nd ed., 2003.DOI
  42. [42]Y. Saad, Multilevel ILU With Reorderings for Diagonal Dominance, SIAM Journal on Scientific Computing, 27 (2005), pp. 1032–1057.DOI
  43. [43]Y. Saad and B. Suchomel, AMRS: an algebraic recursive multilevel solver for general sparse linear systems, Numerical Linear Algebra with Applications, 9 (2002), pp. 359–378.DOI
  44. [44]Y. Saad and J. Zhang, BILUM: Block versions of multielimination and multilevel ILU preconditioner for general sparse linear systems, SIAM Journal on Scientific Computing, 20 (1999), pp. 2103–2121.DOI
  45. [45]S. Thomas, A. Carr, P. Mullowney, R. Li, and K. Świrydowicz, Neumann Series in GMRES and Algebraic Multigrid Smoothers, 2021, https://arxiv.org/abs/2112.14681.
  46. [46]S. Thomas, A. Carr, P. Mullowney, K. Świrydowicz, and M. Day, Scaled ILU smoothers for Navier-Stokes pressure projection, International Journal for Numerical Methods in Fluids, 96 (2024), pp. 537–560.
  47. [47]L. N. Trefethen and M. Embree, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton University Press, Princeton, 2005.
  48. [48]C. R. Trott, D. Lebrun-Grandié, D. Arndt, J. Ciesko, V. Dang, N. Ellingwood, R. Gayatri, E. Harvey, D. S. Hollman, D. Ibanez, N. Liber, J. Madsen, J. Miles, D. Poliakoff, A. Powell, S. Rajamanickam, M. Simberg, D. Sunderland, B. Turksin, and J. Wilke, Kokkos 3: Programming model extensions for the exascale era, IEEE Transactions on Parallel and Distributed Systems, 33 (2022), pp. 805–817.DOI
  49. [49]P. S. Vassilevski, Multilevel Block Factorization Preconditioners: Matrix-based Analysis and Algorithms for Solving Finite Element Equations, Springer, New York, 2008.
  50. [50]T. Zaman, N. Nytko, A. Taghibakhshi, S. MacLachlan, L. Olson, and M. West, Generalizing reduction-based algebraic multigrid, Numerical Linear Algebra with Applications, 31 (2024), p. e2543.arxiv.org/abs/2212.08371
  51. [51]T. U. Zaman, S. P. MacLachlan, L. N. Olson, and M. West, Coarse-grid selection using simulated annealing, Journal of Computational and Applied Mathematics, 431 (2023), p. 115263.arxiv.org/abs/2105.13280

Paper details

vlnc:W_z2ucb4c8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents