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 and 6.8 for ILU(0) and ILU(1)), though this was dominated by smaller problems; on the largest ILU(1) problems all four methods give similar median speedups of 2.1-2.6.
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 into two triangular factors while limiting fill-in (the setup phase). Hence an approximate solution to the linear system can be found with (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 and 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 and 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. and 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 .
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 and 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 and .
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 , 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 and ), 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 and explicitly with an exact level-based incomplete factorisation, ILU(); on the GPU we use the Kokkos Kernels [39, 48] spILUK implementation, which parallelises the factorisation with level-scheduling. The factorisation returns as a unit lower-triangular matrix and with the pivots on its diagonal, so we left-scale 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 and , written for a generic system 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 . A left inverse is computed by minimising over all with a given sparsity pattern. This minimisation decouples into an independent least-squares problem for each row of (or each column for a right inverse). We write as the indices of the nonzero columns in the th row of and as the “shadow” of (i.e., the indices of the nonzero columns in the rows of ) in ; the least-squares problem for row then only involves the small block and determines the nonzero entries .
In this work we only use the “incomplete” SAI (ISAI) [5]; the incomplete version replaces the shadow with , so that the least-squares problem for each row becomes square and is solved exactly by
for the entries of in each row, . An ISAI is typically cheaper to form than a SAI as , and ISAIs can produce better preconditioners than SAIs [5]. We choose a sparsity pattern for in advance, as this fixes the index sets (and hence ) used in each row solve. In this work we build an assembled with the sparsity pattern of itself, rather than that of a higher power of .
Jacobi method/Neumann polynomial
A simple iterative method for solving triangular factors is a Jacobi iteration. As noted in Section 2, both and have been scaled to have a unit diagonal, so for a generic triangular factor we can write , where is strictly triangular (strictly lower for , strictly upper for ). Hence the Jacobi iteration for reduces to , with iteration matrix . Starting from a zero initial guess , after iterations this gives
which is the application of a Neumann polynomial of degree [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 is strictly triangular it is nilpotent, with for a factor of size , so the Neumann series in (2) terminates exactly after terms and the spectral radius of the iteration matrix is zero. Asymptotic convergence is therefore trivially guaranteed, with the iteration exact after at most steps. This is misleading in practice, however, as we only ever apply a low-degree polynomial with and a zero spectral radius says nothing about the size of for small . When is non-normal, as is typically the case for the factors of an ILU factorisation, 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 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 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
where the coefficients are those implicitly constructed by steps of GMRES applied to ; that is, is the GMRES iterate that minimises the residual 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 . This coarse/fine (CF) splitting allows us to write the block system
and form prolongation and restriction operators of the form
The ideal restrictor enforces on F-points, with the ideal prolongator enforcing on F-points. The action of is in general dense and cannot be formed exactly. A practical reduction multigrid therefore replaces it with a sparse approximation and forms approximate ideal grid-transfer operators
AIR methods typically only use in (6) and form a simpler approximation for [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 ). The coarse grid matrix is computed as (which is an approximation to the Schur complement ) and the procedure is applied recursively to build the multigrid hierarchy. To limit fill, entries of and of each coarse grid matrix smaller than a relative drop tolerance ( and , 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, . This ensures that using AIRG in the solve phase only requires SpMVs. Note that approximations to 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 for both, with fill-in controlled by enforcing the sparsity of 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 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 and , parallelising both their setup and solve phases. Consider a lower-triangular factor : if we symmetrically permute (i.e., a reordering) so that each level set is contiguous, 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 on every level. Any independent set of unknowns gives a diagonal , 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 , with its fine rows being the sources of the dependency graph and so having no sub-diagonal entries. The Schur complement then reduces to , 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 , which trade fill against the number of levels. Enforcing 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 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 into factors that are each invertible without fill, so that 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 , 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 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 , 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 in search of even larger F-blocks and fewer levels. They instead select a non-diagonal whose inverse is well behaved, in practice a diagonally dominant block. Such an is no longer trivial to invert exactly, and so its inverse is itself only approximated, by an (incomplete) factorisation of .
Both of these steps move the hierarchy away from an exact solve: dropping the fill makes the elimination incomplete and approximating makes the inversion inexact. The relevant distinction is therefore not whether the solve on each level is exact, but how the (inexact) inverse of is applied. In these multilevel ILU methods the approximate 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 ; each is a self-contained multilevel preconditioner for , 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 or and a triangular solve on every level, which is both redundant and exposes less parallelism.
In contrast, AIRG applied to either the original matrix or to the triangular factors and 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 (with an algorithm detailed in Section 6.2), but then applying the approximate inverse of 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 ) 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 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 and factors they have already (robustly) produced as given and use AIRG to solve them. We leave a study of applying AIRG to directly in these problems for future work. We now consider a parallel CF splitting algorithm for producing diagonally dominant .
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 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 (where is the classical strength-of-connection matrix, in which an off-diagonal entry is strong if for a strength threshold ) such that no large off-diagonal entries appear in the resulting . 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 restricted to the F columns as
where is the vector of C/F markers. The DDC pass takes a user-specified local fraction and swaps at least the worst F rows (by ) back to C; in our implementation it also always swaps every F row with , so the resulting is always diagonally dominant.
For discretisations of advection-dominated PDEs we have found this gives an that is sufficiently diagonally dominant for AIRG to converge well. PMISR DDC, however, gives no control over how diagonally dominant is beyond the fixed bound of one, while the fraction 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 on the maximum diagonal dominance ratio across all rows of ; 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 rather than on 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 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 achieves neither, and we found that using 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 , where is formed from with the strength threshold set to , 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 meets the target . 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 , using the same PMISR routine as in the first pass on , 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 improves as a result are re-evaluated on the next iteration. As PMISR selects the rows with the smallest measure, we invert and use the measure
where is a random value used for tie-breaking and is small enough not to change the relative ordering of rows with distinct . The constant keeps , as PMISR would otherwise classify a row with (normally a row with no strong neighbours) directly as F. Rows already satisfying are assigned and are never swapped. We also tried measuring strength relative to the diagonal in the first pass, , and scaling by the inverse of the number of F-F neighbours to keep 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 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 . 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 directly to the independent set algorithm without ever forming 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 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 . 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 ; this converts at least the worst 10% of F-points to C-points, measured by , along with every F-point with .
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 , initial C/F markers from first-pass PMISR on , target ratio
loop
Extract from using ▷ F rows and F columns of
Compute for every ▷ Eq. (7)
over all ranks ▷ Global reduction
if then exit ▷ meets the target
Initialise swap markers candidate for every
for in parallel do
if then
; keep ▷ Already satisfied, never swapped
else
▷ Eq. (8)
end if
end for
Run PMISR on with measure ▷ Largest first
swap for every candidate in the resulting independent set
for in parallel do
if swap then
Flip from F to C
end if
end for
end loop
factorisation of the matrix. We then run the CF splitting algorithms on the factor (similar results are found for ); this gives the that would be used on the top level of the AIRG multigrid applied to . For consistency we refer to the submatrix as rather than .
Figure 1 shows that the matrix is not diagonally dominant, with many rows having . For this matrix, the PMISR DDC algorithm results in a diagonally dominant matrix, with a maximum equal to 0.998. The DIAG_DOM algorithm, however, gives an matrix which is much more diagonally dominant; the maximum is just below 0.5 (0.500 to three decimal places), which matches the maximum provided threshold . Both CF splittings produce 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 ). 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 and with either splitting, but on the harder factor from ILU(1) it takes 18 iterations with PMISR DDC, compared with 6 with DIAG_DOM (both take 5 on ).

Figure 1. Binned diagonal dominance ratio, , for each row in the lower-triangular factor L produced from an ILU(0) factorisation of the matrix BCSTK24. The maximum across any row in L is 11137 (i.e., L is far from diagonally dominant), but all rows with have been added to the top bin in the figure. The ratio is also shown for the submatrices resulting from a PMISR DDC and DIAG DOM CF splitting on L.
Table 1 shows the effect of sweeping for the DIAG_DOM splitting applied to the same factor of bcsstk24. In every case the achieved maximum matches the requested target to within a tight tolerance. As is decreased the resulting becomes smaller, ranging from around 28% of the unknowns at down to around 12% at . A larger therefore produces a larger , but the resulting block is less diagonally dominant and hence harder to approximate, which degrades the convergence of the resulting AIRG. Conversely, a smaller gives a more diagonally dominant (and more easily inverted) , but extracts fewer F-points on each level. We discuss the implications of this trade-off for parallelism below.
| max | size() | % of unknowns | |
| 0.1 | 0.100 | 418 | 11.73 |
| 0.2 | 0.198 | 524 | 14.71 |
| 0.3 | 0.298 | 599 | 16.82 |
| 0.4 | 0.398 | 709 | 19.90 |
| 0.5 | 0.500 | 744 | 20.89 |
| 0.6 | 0.598 | 815 | 22.88 |
| 0.7 | 0.698 | 874 | 24.54 |
| 0.8 | 0.797 | 948 | 26.61 |
| 0.9 | 0.897 | 1012 | 28.41 |
Table 1. Effect of varying the target diagonal dominance ratio in the DIAG DOM CF splitting, applied to the L factor from an ILU(0) factorisation of BCSTK24. The achieved maximum is rounded to three decimal places; every value is strictly below its .
Parallelism
For AIRG, as noted in § 5.2, controls how diagonally dominant, and hence how large, the resulting block is on each level, and we noted in § 5.1 that the size of sets the available parallelism. A large on each level, paired with an approximation of 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 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 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 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 , , and ), 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 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 with the number of unknowns , 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 or 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 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 .
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 , , , and , 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 with a given source term on the unit square , with Dirichlet boundary conditions. We assemble the discrete operator only on the interior nodes of a uniform grid with spacing . The unknowns are assembled with the natural lexicographic ordering for , where indexes the -direction and the -direction.
Indefinite Helmholtz
The shifted Helmholtz problem is
where is the (real) wavenumber and 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 . Rather than fix in absolute terms, we parameterise the problem by the number of points per wavelength, ppw, and a shift percentage , with
Fixing ppw across refinements means the wavelength always spans the same number of cells, so the problem is equally well resolved at every ; 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 for ppw with , and for ppw with 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 , 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 and factors. For ppw all methods again converge with roughly constant iteration counts under refinement. For the fully indefinite, under-resolved ppw , 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 . ISAI is fairly resilient, converging for and before diverging for . 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.
| ppw | s (%) | N | ordering | AIRG L | AIRG U | GMRES poly L | GMRES poly U | ISAI L | ISAI U | Jacobi L | Jacobi U |
| 4 | 0 | 100 | qmd | 3 | 3 | 1754 | 1901 | 18 | 21 | DIV | DIV |
| 4 | 0 | 200 | qmd | 3 | 3 | MAX | MAX | 23 | 24 | DIV | DIV |
| 4 | 0 | 450 | qmd | 3 | 3 | MAX | MAX | DIV | DIV | DIV | DIV |
| 4 | 0 | 800 | qmd | 3 | 3 | MAX | MAX | DIV | DIV | DIV | DIV |
| 10 | 0 | 100 | colamd | 3 | 3 | 5 | 5 | 16 | 15 | 31 | 30 |
| 10 | 0 | 200 | colamd | 3 | 3 | 7 | 6 | 19 | 17 | 37 | 35 |
| 10 | 0 | 450 | mmd_ata | 3 | 3 | 8 | 8 | 24 | 22 | 48 | 45 |
| 10 | 0 | 800 | nd | 3 | 2 | 5 | 5 | 15 | 14 | 30 | 29 |
| 10 | 5 | 100 | nd | 3 | 2 | 4 | 4 | 12 | 11 | 24 | 23 |
| 10 | 5 | 200 | colamd | 3 | 3 | 6 | 6 | 17 | 16 | 35 | 33 |
| 10 | 5 | 450 | mmd_ata | 3 | 3 | 7 | 7 | 20 | 20 | 43 | 42 |
| 10 | 5 | 800 | mmd_ata | 3 | 3 | 7 | 7 | 21 | 19 | 42 | 40 |
| 10 | 50 | 100 | rcm | 3 | 3 | 13 | 13 | 35 | 35 | 73 | 73 |
| 10 | 50 | 200 | rcm | 3 | 3 | 13 | 13 | 35 | 35 | 74 | 74 |
| 10 | 50 | 450 | natural | 3 | 3 | 13 | 13 | 36 | 36 | 75 | 75 |
| 10 | 50 | 800 | natural | 3 | 3 | 13 | 13 | 36 | 36 | 75 | 75 |
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 , as the grid is refined for each combination of points per wavelength ppw and shift . “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
where is the advection coefficient that controls the strength of the convective term. The advection field 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 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
where is a fixed reference spacing with (the reference grid in [11]). We sweep the grid size for each advection strength ; the values used in [11] correspond to with . Table 3 gives the number of iterations required to solve the and factors for the ILU(1) factorisation; we summarise the ILU(0) results in the text rather than including a table.
| ordering | AIRG L | AIRG U | GMRES poly L | GMRES poly U | ISAI L | ISAI U | Jacobi L | Jacobi U | ||
| 1500 | 100 | rcm | 5 | 3 | 64 | 3 | 103 | 10 | DIV | 19 |
| 200 | rcm | 6 | 3 | 119 | 3 | DIV | 10 | DIV | 20 | |
| 450 | natural | 5 | 2 | 189 | 3 | DIV | 8 | DIV | 18 | |
| 800 | natural | 7 | 2 | 327 | 3 | DIV | 8 | DIV | 18 | |
| 3000 | 100 | rcm | 5 | 4 | 69 | 6 | DIV | 27 | DIV | 80 |
| 200 | rcm | 7 | 4 | 127 | 6 | DIV | 28 | DIV | 83 | |
| 450 | rcm | DIV | 4 | DIV | 6 | DIV | 28 | DIV | 85 | |
| 800 | 1wd | 3 | 5 | 10 | 9 | 42 | 102 | DIV | DIV | |
| 10000 | 100 | rcm | 7 | 7 | 78 | 20 | DIV | DIV | DIV | DIV |
| 200 | rcm | 9 | 7 | 142 | 24 | DIV | DIV | DIV | DIV | |
| 450 | rcm | 12 | 7 | 298 | 26 | DIV | DIV | DIV | DIV | |
| 800 | rcm | 17 | 8 | 512 | 27 | DIV | DIV | DIV | DIV |
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 , as the grid is refined for each advection strength . “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 and . The other methods, by contrast, are not scalable under refinement: for the Jacobi iteration count on the factors grows from 79/36 at to 144/206 at , 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 factor in particular very hard to solve: Jacobi diverges on the factor for every and (and on both factors for and for , ), and ISAI diverges on across almost the entire sweep. GMRES polynomials avoid divergence in all but one case (noted below) but are not scalable, with the iteration count growing steeply under refinement, from 64 to 327 for and from 78 to 512 for . AIRG is the only method that solves both factors with a low, near-constant iteration count throughout, taking 2–7 iterations for and and growing only mildly (from 7 to 17) for the hardest case; the lone exception is , , where both AIRG and GMRES polynomials diverge on in the chosen ordering. The rcm ILU(1) factor at this size is far less stable than at ( reaches for a random , compared with 180), and the residual of both methods initially grows by more than our divergence threshold of . 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 (§ 6.4.2).
The iteration counts above are reported for the ordering that is best for the exact factorisation, chosen afresh at each (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 the ordering changes from RCM to 1WD at , as the RCM ILU(1)-preconditioned solve diverges; this, rather than the grid size, is responsible for the drop in the GMRES polynomial iteration count on from 127 at to 10 at . 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 ). With 1WD fixed at every , AIRG solves the factors in 3 and 5 iterations independent of , whereas the GMRES polynomial grows from 7 to 10 iterations on , ISAI from 48 to 102 on , and Jacobi diverges on both factors from . Conversely, for , where the chosen ordering at and 800 is NATURAL, fixing RCM instead gives ILU(1) factors on which AIRG and the GMRES polynomial also diverge at those sizes.
Table 4 isolates the effect of the ordering for the , , ILU(0) problem. Of the nine orderings we tested, only three (QMD, ND and COLAMD) produce an ILU(0) factorisation for which the 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 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.
| ordering | AIRG L | AIRG U | GMRES poly L | GMRES poly U | ISAI L | ISAI U | Jacobi L | Jacobi U | AIRG L | AIRG U | level sets |
| qmd | 1 | 1 | 2 | 2 | 4 | 4 | 8 | 8 | 5 | 5 | 8 |
| nd | 2 | 2 | 1 | 1 | 3 | 4 | 6 | 6 | 5 | 5 | 6 |
| colamd | 3 | 3 | 37 | 16 | 58 | 45 | 115 | 90 | 7 | 6 | 123 |
Table 4. The effect of the unknown ordering on the ILU(0) factors of the advection-diffusion problem (7.3) with , , 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 level sets, growing from 199 at to 1599 at , whereas, as discussed in § 5.4, the number of levels in a multigrid hierarchy grows only logarithmically.
Anisotropic diffusion
The anisotropic diffusion problem is
where is the anisotropy ratio; is the strong direction and the weak direction. We use a second-order central-difference 5-point stencil, which gives a symmetric positive definite matrix, and we set to produce very anisotropic diffusion. We sweep the grid size 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.
| AIRG | GMRES poly | ISAI | Jacobi | |||||
| L | U | L | U | L | U | L | U | |
| 100 | 2 | 2 | 40 | 39 | 50 | 50 | 100 | 100 |
| 200 | 2 | 2 | 72 | 72 | 100 | 100 | 200 | 200 |
| 450 | 2 | 2 | 150 | 149 | 225 | 225 | 450 | 450 |
| 800 | 2 | 2 | 256 | 255 | 400 | 400 | 800 | 800 |
Table 5. For the anisotropic diffusion problem (7.5) with the number of iterations to solve the L and U factors generated by an ILU(0) factorisation to a relative tolerance of , as the grid is refined (the winning ordering is natural at every ). “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 . 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 to 800 at , 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 and 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 or 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 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 and factors could be solved, we take the larger of the and 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 and 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 and 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, ) 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 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.

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 . 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 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) | |||||||
| Method | Conv. | Fastest | All | Conv. | Fastest | All | ||
| Exact | 66 | 5 | 1 | 1 | 71 | 5 | 1 | 1 |
| AIRG | 64 | 0 | 1.1 | 1.2 | 69 | 2 | 1.4 | 2.3 |
| Jacobi | 63 | 4 | 2.6 | 2.2 | 65 | 3 | 3.2 | 2.3 |
| GMRES poly | 67 | 6 | 3.0 | 2.4 | 71 | 12 | 5.0 | 2.1 |
| ISAI | 67 | 52 | 4.5 | 2.7 | 70 | 50 | 6.8 | 2.6 |
Table 6. Summary of the 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 . Jacobi, ISAI and the GMRES polynomial use the best number of inner iterations for each problem.

Figure SM2. Solve time comparison (smaller is better) for the 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 and 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 are shown. Table 6 of the article summarises these results.

Figure SM3. Solve time comparison (smaller is better) for the 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 and 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 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 for the problems with to for those with with ILU(0), and from to with ILU(1). The speedups of ISAI and the GMRES polynomials fall on the largest problems, most of all for ISAI, from to with ILU(0) and from to 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 faster than AIRG for but only faster for with ILU(0), and and faster with ILU(1); on the largest problems with ILU(1) all four iterative methods give similar median speedups, between and . 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 and 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 with a single parameter, , 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 for ILU(0) and for ILU(1), and where it was faster its larger setup cost took a median of 28.4 and 24.1 solves of 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 for ILU(0) and for ILU(1). This advantage comes mainly from the smaller problems, where kernel launch times can dominate: on the problems with the speedups of the four methods are closer. For example, for ILU(1), all four iterative methods produced median speedups of between and 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 (§ 6.4.2 of the article), each factor is instead solved with a fixed number of iterations and without computing any norms or dot products: for (and always for the single V-cycle of AIRG) we use
-ksp_type preonly
and for
-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 -order GMRES polynomial () on all levels except the coarsest. With the DIAG-DOM CF splitting, -pc_air_strong_threshold sets both the strength threshold and the maximum diagonal dominance ratio of Algorithm 6.1 of the article (); the value 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 , and if so we truncate the hierarchy there. The coarse-grid solver is a -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 -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 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 and 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 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 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 , and , 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, .
| # | Matrix | ordering | AIRG L | AIRG U | GMRES poly L | GMRES poly U | ISAI L | ISAI U | Jacobi L | Jacobi U |
| 1 | 1138_bus | mmd_ata | 2 | 2 | 2 | 2 | 5 | 5 | 9 | 10 |
| 2 | bcsstk19 | natural | 5 | 4 | MAX | MAX | 63 | 68 | 155 | 157 |
| 3 | Chem97ZtZ | natural | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 |
| 4 | bcsstk08 | 1wd | 2 | 3 | 4 | 12 | 7 | 7 | 17 | 16 |
| 5 | mhd3200b | rcm | 6 | 6 | 4 | 5 | 8 | 9 | 21 | 22 |
| 6 | bcsstm12 | nd | 3 | 4 | 11 | 18 | 5 | 5 | 33 | 34 |
| 7 | bcsstk10 | rcm | 4 | 4 | 94 | 40 | 29 | 29 | DIV | DIV |
| 8 | mhd4800b | rcm | 6 | 6 | 4 | 7 | 9 | 9 | 22 | 23 |
| 9 | msc01050 | natural | 3 | 3 | 761 | 1219 | 8 | 8 | 24 | 24 |
| 10 | plbuckle | natural | 3 | 5 | 16 | 78 | 15 | 15 | 41 | 42 |
| 11 | Trefethen_2000 | natural | 2 | 2 | 1 | 2 | 3 | 4 | 6 | 8 |
| 12 | bcsstk27 | natural | 3 | 3 | 22 | 19 | 20 | 20 | DIV | DIV |
| 13 | bcsstk14 | rowlength | 2 | 3 | 3 | 3 | 7 | 7 | 16 | 16 |
| 14 | nasa2146 | natural | 3 | 3 | 17 | 14 | 20 | 20 | 62 | 60 |
| 15 | fv1 | natural | 2 | 2 | 3 | 3 | 10 | 10 | 22 | 22 |
| 16 | fv2 | natural | 2 | 2 | 3 | 3 | 10 | 10 | 22 | 22 |
| 17 | msc04515 | nd | 3 | 5 | MAX | MAX | 20 | 18 | DIV | DIV |
| 18 | crystm01 | natural | 3 | 3 | 5 | 5 | 9 | 9 | 36 | 36 |
| 19 | bcsstk15 | colamd | 3 | 3 | 7 | 7 | 8 | 9 | 20 | 19 |
| 20 | bodyy4 | natural | 3 | 2 | 9 | 7 | 13 | 15 | 26 | 30 |
| # | Matrix | ordering | AIRG L | AIRG U | GMRES poly L | GMRES poly U | ISAI L | ISAI U | Jacobi L | Jacobi U |
| 21 | aft01 | rcm | 4 | 4 | 23 | 25 | 108 | DIV | DIV | DIV |
| 22 | bodyy5 | natural | 2 | 2 | 20 | 11 | 15 | 18 | 30 | 37 |
| 23 | bodyy6 | natural | 3 | 2 | 33 | 14 | 19 | 21 | 38 | 41 |
| 24 | ted_B | natural | 3 | 2 | 3 | 3 | 5 | 5 | 17 | 18 |
| 25 | ted_B_unscaled | natural | 3 | 2 | 3 | 3 | 5 | 5 | 17 | 18 |
| 26 | bcsstk18 | natural | 3 | 3 | 6 | 20 | 11 | 12 | 25 | 24 |
| 27 | bcsstk24 | rcm | 5 | 5 | MAX | MAX | 19 | 17 | DIV | 107 |
| 28 | Muu | rcm | 3 | 3 | 3 | 3 | 6 | 6 | 19 | 19 |
| 29 | t2dah_e | rcm | 4 | 5 | 5 | 5 | 52 | 58 | DIV | DIV |
| 30 | obstclae | natural | 2 | 2 | 4 | 4 | 12 | 12 | 23 | 23 |
| 31 | torsion1 | natural | 2 | 2 | 4 | 4 | 12 | 12 | 23 | 23 |
| 32 | jnlbrng1 | natural | 2 | 2 | 7 | 7 | 19 | 19 | 37 | 37 |
| 33 | minsurfo | natural | 3 | 3 | 4 | 4 | 12 | 12 | 24 | 24 |
| 34 | s3rmt3m3 | rcm | 9 | 7 | MAX | DIV | 33 | 30 | DIV | DIV |
| 35 | s1rmt3m1 | natural | 4 | 4 | 17 | 24 | 18 | 18 | 74 | 74 |
| 36 | s2rmt3m1 | natural | 5 | 4 | 1619 | 51 | 19 | 18 | 87 | 86 |
| 37 | s3rmt3m1 | natural | 6 | 9 | MAX | MAX | 17 | 17 | DIV | DIV |
| 38 | Dubcova1 | rcm | 3 | 3 | 7 | 7 | 16 | 16 | 49 | 49 |
| 39 | s1rmq4m1 | natural | 4 | 4 | 35 | 64 | 20 | 21 | 83 | 86 |
| 40 | s2rmq4m1 | natural | 6 | 5 | MAX | 77 | 20 | 20 | 75 | 71 |
| 41 | s3rmq4m1 | natural | 9 | 9 | DIV | DIV | 20 | 20 | DIV | DIV |
| 42 | chipcool0 | 1wd | 3 | 3 | 4 | 4 | 13 | 12 | 29 | 28 |
| 43 | bcsstk16 | natural | 3 | 3 | 6 | 7 | 18 | 19 | 41 | 39 |
| 44 | crystm02 | natural | 3 | 3 | 5 | 5 | 9 | 9 | 47 | 47 |
| 45 | shallow_water1 | natural | 2 | 2 | 2 | 2 | 5 | 5 | 9 | 9 |
| 46 | shallow_water2 | rcm | 2 | 2 | 3 | 3 | 9 | 9 | 17 | 17 |
| 47 | Kuu | rowlength | 3 | 3 | 3 | 3 | 6 | 5 | 16 | 15 |
| 48 | gyro_m | 1wd | 4 | 3 | 7 | 7 | 33 | 32 | DIV | DIV |
| 49 | bcsstk17 | nd | 3 | 3 | 109 | 86 | 10 | 9 | 59 | DIV |
| 50 | wathen100 | natural | 4 | 4 | 4 | 4 | 44 | 45 | DIV | DIV |
| 51 | gridgena | rcm | 3 | 3 | 6 | 6 | 15 | 15 | 42 | 39 |
| 52 | apache1 | rcm | 2 | 3 | 3 | 4 | 9 | 10 | 18 | 20 |
| 53 | Trefethen_20000 | colamd | 2 | 1 | 1 | 1 | 3 | 3 | 6 | 6 |
| 54 | wathen120 | natural | 4 | 4 | 4 | 4 | 45 | 45 | DIV | DIV |
| 55 | thermal1 | rcm | 3 | 3 | 5 | 5 | 14 | 14 | 31 | 31 |
| 56 | crystm03 | natural | 3 | 3 | 5 | 5 | 9 | 9 | 52 | 52 |
| 57 | finan512 | natural | 2 | 2 | 2 | 2 | 4 | 4 | 8 | 8 |
| 58 | cbuckle | qmd | 3 | 4 | 77 | 141 | 8 | 8 | DIV | DIV |
| 59 | thermomech_TC | rcm | 2 | 2 | 2 | 2 | 8 | 8 | 18 | 19 |
| 60 | thermomech_TK | rcm | 3 | 3 | 5 | 5 | 15 | 15 | 32 | 32 |
| 61 | Pres_Poisson | rcm | 4 | 4 | 18 | 11 | 20 | 19 | DIV | DIV |
| 62 | bundle1 | qmd | 2 | 2 | 2 | 2 | 3 | 3 | 10 | 9 |
| 63 | bcsstk36 | 1wd | DIV | DIV | DIV | MAX | DIV | DIV | DIV | DIV |
| 64 | cfd1 | 1wd | 5 | 5 | 31 | 31 | 56 | 56 | DIV | DIV |
| 65 | bcsstk39 | mmd_ata | 5 | 6 | MAX | MAX | 31 | 31 | DIV | DIV |
| 66 | nd3k | natural | 4 | 4 | 265 | 217 | DIV | DIV | DIV | DIV |
| 67 | parabolic_fem | rcm | 3 | 3 | 8 | 8 | 22 | 22 | 46 | 46 |
| 68 | offshore | 1wd | 3 | 3 | 5 | 4 | 13 | 11 | 30 | 26 |
| 69 | apache2 | natural | 2 | 2 | 4 | 4 | 12 | 12 | 24 | 24 |
| 70 | ecology2 | rcm | 3 | 3 | 5 | 5 | 13 | 13 | 26 | 26 |
| 71 | G3_circuit | natural | 3 | 3 | 10 | 9 | 31 | 29 | 62 | 57 |
| 72 | thermal2 | 1wd | 3 | 3 | 4 | 4 | 13 | 13 | 29 | 29 |
| 73 | crankseg_1 | rcm | 3 | DNF | 21 | 19 | 22 | 19 | DIV | DIV |
| 74 | crankseg_2 | rcm | DNF | DNF | 24 | 22 | 25 | 22 | DIV | DIV |
| 75 | af_shell3 | rcm | 3 | 3 | 8 | 8 | 26 | 26 | 68 | 68 |
| 76 | StocF-1465 | rcm | 4 | 2 | MAX | 21 | 35 | 33 | 73 | 68 |
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 . “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.
| # | Matrix | nnz | Application area | |
| 1 | 1138_bus | 1 138 | 4 054 | Power-system network |
| 2 | bcsstk19 | 817 | 6 853 | Structural (part of a suspension bridge) |
| 3 | Chem97ZtZ | 2 541 | 7 361 | Statistics (normal equations) |
| 4 | bcsstk08 | 1 074 | 12 960 | Structural (TV studio) |
| 5 | mhd3200b | 3 200 | 18 316 | Magnetohydrodynamics |
| 6 | bcsstm12 | 1 473 | 19 659 | Structural (mass matrix) |
| 7 | bcsstk10 | 1 086 | 22 070 | Structural mechanics (buckling) |
| 8 | mhd4800b | 4 800 | 27 520 | Magnetohydrodynamics |
| 9 | msc01050 | 1 050 | 29 156 | Structural mechanics |
| 10 | plbuckle | 1 282 | 30 644 | Structural (buckling plate) |
| 11 | Trefethen_2000 | 2 000 | 41 906 | Combinatorics (Trefethen) |
| 12 | bcsstk27 | 1 224 | 56 126 | Structural (buckling) |
| 13 | bcsstk14 | 1 806 | 63 454 | Structural (roof of Omni Coliseum) |
| 14 | nasa2146 | 2 146 | 72 250 | Structural mechanics |
| 15 | fv1 | 9 604 | 85 264 | 2D finite-volume mesh |
| 16 | fv2 | 9 801 | 87 025 | 2D finite-volume mesh |
| 17 | msc04515 | 4 515 | 97 707 | Structural mechanics |
| 18 | crystm01 | 4 875 | 105 339 | Materials (crystal mass matrix) |
| 19 | bcsstk15 | 3 948 | 117 816 | Structural (module of an offshore platform) |
| 20 | bodyy4 | 17 546 | 121 938 | Structural (FE mesh) |
| 21 | aft01 | 8 205 | 125 567 | Acoustics (vibroacoustics) |
| 22 | bodyy5 | 18 589 | 129 281 | Structural (FE mesh) |
| 23 | bodyy6 | 19 366 | 134 748 | Structural (FE mesh) |
| 24 | ted_B | 10 605 | 144 579 | Thermal model reduction |
| 25 | ted_B_unscaled | 10 605 | 144 579 | Thermal model reduction (unscaled) |
| 26 | bcsstk18 | 11 948 | 149 090 | Structural (R.E. Ginna nuclear power station) |
| 27 | bcsstk24 | 3 562 | 159 910 | Structural (Calgary Olympic Saddledome arena) |
| 28 | Muul | 7 102 | 170 134 | Structural (FEM mass matrix) |
| # | Matrix | nnz | Application area | |
| 29 | t2dah_e | 11 445 | 176 117 | Model reduction (micropyros thruster) |
| 30 | obstclae | 40 000 | 197 608 | Obstacle problem (optimisation) |
| 31 | torsion1 | 40 000 | 197 608 | Torsion (optimisation) |
| 32 | jnlbrng1 | 40 000 | 199 200 | Journal-bearing (optimisation) |
| 33 | minsurfo | 40 806 | 203 622 | Minimal-surface (optimisation) |
| 34 | s3rmt3m3 | 5 357 | 207 695 | Structural (cylindrical shell) |
| 35 | s1rmt3m1 | 5 489 | 219 521 | Structural (cylindrical shell) |
| 36 | s2rmt3m1 | 5 489 | 219 521 | Structural (cylindrical shell) |
| 37 | s3rmt3m1 | 5 489 | 219 521 | Structural (cylindrical shell) |
| 38 | Dubcova1 | 16 129 | 253 009 | 2D/3D PDE |
| 39 | s1rmq4m1 | 5 489 | 281 111 | Structural (cylindrical shell) |
| 40 | s2rmq4m1 | 5 489 | 281 111 | Structural (cylindrical shell) |
| 41 | s3rmq4m1 | 5 489 | 281 111 | Structural (cylindrical shell) |
| 42 | chipcool0 | 20 082 | 281 150 | Thermal model reduction |
| 43 | bcsstk16 | 4 884 | 290 378 | Structural (Corps of Engineers dam) |
| 44 | crystm02 | 13 965 | 322 905 | Materials (crystal mass matrix) |
| 45 | shallow-water1 | 81 920 | 327 680 | Climate (shallow-water) |
| 46 | shallow-water2 | 81 920 | 327 680 | Climate (shallow-water) |
| 47 | Kuu | 7 102 | 340 200 | Structural (FEM stiffness) |
| 48 | gyro_m | 17 361 | 340 431 | Model reduction (gyroscope mass matrix) |
| 49 | bcsstk17 | 10 974 | 428 650 | Structural (elevated pressure vessel) |
| 50 | wathen100 | 30 401 | 471 601 | Structural (Wathen FE) |
| 51 | gridgena | 48 962 | 512 084 | Optimisation (grid generation) |
| 52 | apache1 | 80 800 | 542 184 | 3D structural mechanics |
| 53 | Trefethen_20000 | 20 000 | 554 466 | Combinatorics (Trefethen) |
| 54 | wathen120 | 36 441 | 565 761 | Structural (Wathen FE) |
| 55 | thermal1 | 82 654 | 574 458 | Steady-state thermal |
| 56 | crystm03 | 24 696 | 583 770 | Materials (crystal mass matrix) |
| 57 | finan512 | 74 752 | 596 992 | Financial portfolio optimisation |
| 58 | cbuckle | 13 681 | 676 515 | Structural (buckling) |
| 59 | thermomech_TC | 102 158 | 711 558 | Thermomechanical |
| 60 | thermomech_TK | 102 158 | 711 558 | Thermomechanical |
| 61 | Pres_Poisson | 14 822 | 715 804 | CFD (pressure Poisson) |
| 62 | bundle1 | 10 581 | 770 901 | Computer vision (bundle adjustment) |
| 63 | bcsstk36 | 23 052 | 1 143 140 | Structural (automobile shock absorber) |
| 64 | cfd1 | 70 656 | 1 828 364 | CFD pressure matrix |
| 65 | bcsstk39 | 46 772 | 2 089 294 | Structural (solid element model) |
| 66 | nd3k | 9 000 | 3 279 690 | 3D mesh problem (ND set) |
| 67 | parabolic_fem | 525 825 | 3 674 625 | Parabolic FEM, convection-diffusion |
| 68 | offshore | 259 789 | 4 242 673 | Electromagnetics (offshore EM survey) |
| 69 | apache2 | 715 176 | 4 817 870 | 3D structural mechanics |
| 70 | ecology2 | 999 999 | 4 995 991 | 2D circular food-web model |
| 71 | G3_circuit | 1 585 478 | 7 660 826 | Circuit simulation |
| 72 | thermal2 | 1 228 045 | 8 580 313 | Steady-state thermal |
| 73 | crankseg_1 | 52 804 | 10 614 210 | Structural (crank segment) |
| 74 | crankseg_2 | 63 838 | 14 148 858 | Structural (crank segment) |
| 75 | af_shell3 | 504 855 | 17 588 875 | Structural (sheet-metal forming) |
| 76 | StocF-1465 | 1 465 137 | 21 005 389 | Fluid flow (stochastic FEM) |
Table SM1. The symmetric SuiteSparse/Matrix Market test matrices (numbers 1 to 76), with the size 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.
| # | Matrix | ordering | AIRG L | AIRG U | GMRES poly L | GMRES poly U | ISAI L | ISAI U | Jacobi L | Jacobi U |
| 1 | 1138_bus | rcm | 3 | 2 | 238 | 7 | 17 | 16 | 37 | 32 |
| 2 | bcsstk19 | rcm | 4 | 4 | MAX | MAX | 45 | 45 | DIV | DIV |
| 3 | Chem97ZtZ | natural | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 |
| 4 | bcsstk08 | rcm | 3 | 3 | 5 | 21 | 7 | 7 | 16 | 17 |
| 5 | mhd3200b | natural | 6 | 6 | 5 | 6 | 8 | 9 | 19 | 22 |
| 6 | bcsstm12 | nd | 2 | 3 | 11 | 17 | 4 | 4 | 33 | 34 |
| 7 | bcsstk10 | 1wd | 3 | 3 | 12 | 26 | 6 | 6 | 28 | 28 |
| 8 | mhd4800b | natural | 6 | 6 | 5 | 7 | 9 | 9 | 20 | 22 |
| 9 | msc01050 | qmd | 2 | 3 | 8 | 10 | 7 | 8 | 31 | 32 |
| 10 | plbuckle | natural | 4 | 5 | 10 | 21 | 16 | 16 | 43 | 46 |
| 11 | Trefethen_2000 | nd | 2 | 2 | 1 | 1 | 3 | 3 | 6 | 6 |
| 12 | bcsstk27 | natural | 4 | 4 | 36 | 23 | 21 | 21 | DIV | DIV |
| 13 | bcsstk14 | rcm | 3 | 3 | 11 | 21 | 16 | 16 | 45 | 50 |
| 14 | nasa2146 | natural | 3 | 3 | 18 | 14 | 17 | 17 | 61 | 59 |
| 15 | fv1 | natural | 2 | 2 | 4 | 4 | 11 | 11 | 26 | 26 |
| 16 | fv2 | natural | 2 | 2 | 4 | 4 | 11 | 11 | 26 | 26 |
| 17 | msc04515 | rcm | 5 | 4 | 138 | 46 | 28 | 26 | DIV | DIV |
| 18 | crystm01 | natural | 3 | 3 | 5 | 5 | 6 | 6 | 36 | 36 |
| 19 | bcsstk15 | rcm | 4 | 4 | 44 | 20 | 14 | 14 | 36 | 38 |
| 20 | bodyy4 | natural | 3 | 3 | 9 | 7 | 13 | 15 | 26 | 30 |
| 21 | aft01 | natural | 6 | 3 | 29 | 30 | 78 | 79 | DIV | DIV |
| 22 | bodyy5 | natural | 3 | 2 | 20 | 11 | 15 | 18 | 30 | 36 |
| 23 | bodyy6 | natural | 3 | 2 | 33 | 14 | 19 | 21 | 38 | 41 |
| 24 | ted_B | natural | 3 | 2 | 3 | 3 | 5 | 5 | 17 | 18 |
| 25 | ted_B_unscaled | natural | 3 | 2 | 3 | 3 | 5 | 5 | 17 | 18 |
| 26 | bcsstk18 | mmd_at_plus_a | 3 | 3 | 95 | 7 | 8 | 7 | 19 | 17 |
| 27 | bcsstk24 | rcm | 6 | 5 | MAX | MAX | 27 | 26 | DIV | DIV |
| 28 | Muu | rcm | 3 | 3 | 3 | 3 | 6 | 6 | 19 | 19 |
| 29 | t2dah_e | natural | 3 | 4 | 3 | 3 | 7 | 7 | 95 | 144 |
| 30 | obstclae | natural | 3 | 3 | 6 | 6 | 17 | 17 | 35 | 35 |
| 31 | torsion1 | natural | 3 | 3 | 6 | 6 | 17 | 17 | 35 | 35 |
| 32 | jnlbrng1 | natural | 3 | 3 | 12 | 12 | 33 | 33 | 66 | 66 |
| 33 | minsurfo | natural | 3 | 3 | 6 | 6 | 18 | 18 | 37 | 37 |
| 34 | s3rmt3m3 | rcm | 9 | 8 | MAX | DIV | 36 | 32 | DIV | DIV |
| 35 | s1rmt3m1 | rcm | 4 | 4 | 80 | 30 | 32 | 31 | 91 | 90 |
| 36 | s2rmt3m1 | natural | 4 | 4 | MAX | 171 | 23 | 21 | 93 | 92 |
| 37 | s3rmt3m1 | natural | 8 | 10 | MAX | DIV | 22 | 20 | DIV | DIV |
| 38 | Dubcova1 | rcm | 3 | 3 | 9 | 9 | 22 | 20 | 51 | 50 |
| 39 | s1rmq4m1 | natural | 4 | 4 | 84 | 89 | 22 | 22 | 82 | 83 |
| 40 | s2rmq4m1 | natural | 6 | 6 | MAX | 170 | 23 | 22 | 106 | 102 |
| 41 | s3rmq4m1 | natural | 9 | DNF | MAX | DIV | 24 | 23 | DIV | DIV |
| 42 | chipcool0 | natural | 3 | 3 | 7 | 7 | 20 | 20 | 50 | 50 |
| 43 | bcsstk16 | natural | 3 | 3 | 9 | 9 | 22 | 23 | 53 | 53 |
| 44 | crystm02 | natural | 3 | 3 | 5 | 5 | 6 | 6 | 47 | 47 |
| 45 | shallow_water1 | rcm | 2 | 2 | 2 | 2 | 6 | 6 | 11 | 11 |
| 46 | shallow_water2 | rcm | 2 | 3 | 3 | 3 | 10 | 10 | 19 | 19 |
| 47 | Kuu | 1wd | 3 | 3 | 17 | 17 | 22 | 23 | 96 | 92 |
| 48 | gyro_m | natural | 3 | 3 | 13 | 11 | 21 | 20 | DIV | DIV |
| 49 | bcsstk17 | rowlength | 3 | 4 | 365 | 76 | 15 | 14 | DIV | DIV |
| 50 | wathen100 | natural | 4 | 4 | 4 | 4 | 21 | 21 | DIV | DIV |
| 51 | gridgena | qmd | 2 | 2 | 3 | 3 | 8 | 9 | 19 | 21 |
| 52 | apache1 | rcm | 3 | 3 | 4 | 5 | 13 | 14 | 27 | 30 |
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 . “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.
| # | Matrix | ordering | AIRG L | AIRG U | GMRES poly L | GMRES poly U | ISAI L | ISAI U | Jacobi L | Jacobi U |
| 53 | Trefethen_20000 | natural | 2 | 2 | 1 | 2 | 3 | 4 | 6 | 8 |
| 54 | wathen120 | natural | 4 | 4 | 4 | 4 | 21 | 21 | DIV | DIV |
| 55 | thermal1 | 1wd | 3 | 3 | 7 | 6 | 19 | 19 | 44 | 44 |
| 56 | crystm03 | natural | 3 | 3 | 5 | 5 | 6 | 6 | 52 | 52 |
| 57 | finan512 | natural | 2 | 2 | 2 | 2 | 4 | 4 | 8 | 8 |
| 58 | cbuckle | rcm | 4 | 4 | 794 | MAX | 22 | 23 | DIV | DIV |
| 59 | thermomech_TC | rcm | 2 | 2 | 2 | 2 | 7 | 7 | 17 | 17 |
| 60 | thermomech_TK | rcm | 3 | 3 | 7 | 7 | 22 | 22 | 50 | 49 |
| 61 | Pres_Poisson | rcm | 5 | 3 | 20 | 14 | 26 | 25 | DIV | DIV |
| 62 | bundle1 | rowlength | 2 | 2 | 2 | 2 | 3 | 3 | 12 | 12 |
| 63 | bcsstk36 | rcm | 8 | 9 | DIV | DIV | DIV | DIV | DIV | DIV |
| 64 | cfd1 | 1wd | 5 | 5 | 49 | 51 | 53 | 54 | DIV | DIV |
| 65 | bcsstk39 | nd | 4 | 5 | MAX | MAX | DIV | DIV | DIV | DIV |
| 66 | nd3k | natural | 3 | 3 | 133 | 95 | DIV | DIV | DIV | DIV |
| 67 | parabolic_fem | rcm | 4 | 3 | 11 | 11 | 31 | 31 | 66 | 66 |
| 68 | offshore | natural | 4 | 4 | 40 | 64 | 28 | 29 | 83 | DIV |
| 69 | apache2 | natural | 3 | 3 | 6 | 6 | 18 | 19 | 38 | 40 |
| 70 | ecology2 | natural | 3 | 3 | 8 | 8 | 22 | 22 | 46 | 46 |
| 71 | G3_circuit | natural | 4 | 3 | 10 | 9 | 32 | 30 | 63 | 59 |
| 72 | thermal2 | rcm | 3 | 3 | 7 | 7 | 21 | 21 | 49 | 48 |
| 73 | crankseg_1 | rcm | DNF | DNF | 22 | 20 | 19 | 18 | DIV | DIV |
| 74 | crankseg_2 | rcm | DNF | DNF | 26 | 23 | 21 | 19 | DIV | DIV |
| 75 | af_shell3 | rcm | 3 | 3 | 10 | 10 | 32 | 32 | 96 | 94 |
| 76 | StocF-1465 | rcm | 5 | 3 | MAX | 23 | 41 | 37 | 94 | 80 |
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 . “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.
| # | Matrix | nnz | Application area | |
| 77 | cage10 | 11 397 | 150 645 | DNA electrophoresis |
| 78 | cage11 | 39 082 | 559 722 | DNA electrophoresis |
| 79 | ASIC_100ks | 99 190 | 578 890 | Circuit simulation |
| 80 | trans4 | 116 835 | 766 396 | Circuit simulation |
| # | Matrix | nnz | Application area | |
| 81 | torso2 | 115 967 | 1 033 473 | Bioengineering (electrocardiology) |
| 82 | 3D_51448_3D | 51 448 | 1 056 610 | Structural (3D problem) |
| 83 | venkat01 | 62 424 | 1 717 792 | CFD (unstructured 2D Euler) |
| 84 | majorbasis | 160 000 | 1 750 416 | Optimisation |
| 85 | poisson3Db | 85 623 | 2 374 949 | CFD (3D Poisson) |
| 86 | stomach | 213 360 | 3 021 648 | Bioengineering (3D EM model of duodenum) |
| 87 | tmt_unsym | 917 825 | 4 584 801 | Electromagnetics |
| 88 | atmosmodd | 1 270 432 | 8 814 880 | Atmospheric modelling |
| 89 | Freescale1 | 3 428 755 | 18 920 347 | Circuit simulation |
| 90 | CoupCons3D | 416 800 | 22 322 336 | Structural (coupled consolidation) |
| 91 | Transport | 1 602 111 | 23 500 731 | Structural (3D transport) |
Table SM2.
| # | Matrix | ordering | AIRG L | AIRG U | GMRES poly L | GMRES poly U | ISAI L | ISAI U | Jacobi L | Jacobi U |
| 77 | cage10 | natural | 2 | 2 | 2 | 2 | 5 | 5 | 10 | 11 |
| 78 | cage11 | natural | 2 | 2 | 2 | 2 | 5 | 5 | 10 | 11 |
| 79 | ASIC_100ks | rcm | 2 | 2 | 150 | 2 | 9 | 5 | 18 | 11 |
| 80 | trans4 | rcm | 2 | 2 | 1 | 2 | 3 | 4 | 7 | 8 |
| 81 | torso2 | natural | 2 | 2 | 3 | 3 | 7 | 7 | 16 | 16 |
| 82 | 3D_51448_3D | rowlength | 5 | 3 | MAX | 6 | 16 | 16 | 57 | 32 |
| 83 | venkat01 | rcm | 5 | 4 | 11 | 14 | 29 | 33 | 59 | 82 |
| 84 | majorbasis | rcm | 3 | 3 | 6 | 5 | 16 | 13 | 39 | 27 |
| 85 | poisson3Db | 1wd | 2 | 3 | 4 | 3 | 9 | 9 | 23 | 21 |
| 86 | stomach | rcm | 3 | 3 | 5 | 5 | 14 | 14 | 27 | 28 |
| 87 | tmt_unsym | rcm | 3 | 3 | 5 | 5 | 13 | 13 | 26 | 26 |
| 88 | atmosmodd | rcm | 2 | 2 | 4 | 4 | 13 | 12 | 25 | 24 |
| 89 | Freescale1 | natural | 2 | 2 | 11 | 11 | 33 | 32 | 66 | 63 |
| 90 | CoupCons3D | natural | 3 | 4 | 6 | 7 | 17 | 18 | 37 | 41 |
| 91 | Transport | rcm | 3 | 3 | 7 | 7 | 21 | 21 | 44 | 44 |
Table SM5 (PDF p. 31).
| # | Matrix | ordering | AIRG L | AIRG U | GMRES poly L | GMRES poly U | ISAI L | ISAI U | Jacobi L | Jacobi U |
| 77 | cage10 | natural | 2 | 2 | 2 | 2 | 4 | 5 | 9 | 9 |
| 78 | cage11 | natural | 2 | 2 | 2 | 2 | 4 | 5 | 9 | 9 |
| 79 | ASIC_100ks | natural | 2 | 2 | 196 | 2 | 8 | 5 | 15 | 10 |
| 80 | trans4 | rcm | 2 | 2 | 2 | 2 | 4 | 4 | 13 | 13 |
| 81 | torso2 | rcm | 2 | 2 | 3 | 3 | 7 | 7 | 17 | 17 |
| 82 | 3D_51448_3D | natural | 5 | 4 | MAX | 10 | 24 | 21 | DIV | 44 |
| 83 | venkat01 | rcm | 5 | 4 | 13 | 16 | 34 | 36 | 70 | 89 |
| 84 | majorbasis | rcm | 3 | 3 | 7 | 5 | 16 | 15 | 42 | 30 |
| 85 | poisson3Db | natural | 2 | 2 | 3 | 3 | 6 | 6 | 19 | 19 |
| 86 | stomach | rcm | 3 | 3 | 5 | 5 | 13 | 14 | 30 | 29 |
| 87 | tmt_unsym | rcm | 3 | 3 | 8 | 8 | 22 | 22 | 46 | 46 |
| 88 | atmosmodd | rcm | 3 | 3 | 7 | 7 | 21 | 20 | 42 | 42 |
| 89 | Freescale1 | natural | 2 | 2 | 14 | 14 | 43 | 41 | 86 | 81 |
| 90 | CoupCons3D | natural | 3 | 4 | 7 | 8 | 18 | 20 | 35 | 38 |
| 91 | Transport | rcm | 3 | 3 | 11 | 11 | 30 | 30 | 64 | 64 |
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 . “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 solve time for each test matrix, summarised in Table 6 and discussed in Section 7.4.2 of the article.

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]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]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]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]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]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]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]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]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]E. Chow, A Priori Sparsity Patterns for Parallel Sparse Approximate Inverse Preconditioners, SIAM Journal on Scientific Computing, 21 (2000), pp. 1804–1822.DOI
- [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]E. Chow and A. Patel, Fine-Grained Parallel Incomplete LU Factorization, SIAM Journal on Scientific Computing, 37 (2015), pp. C169–C193.DOI
- [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]E. Chow and Y. Saad, Approximate Inverse Preconditioners via Sparse-Sparse Iterations, SIAM Journal on Scientific Computing, 19 (1998), pp. 995–1023.DOI
- [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]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]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]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]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]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]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]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]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]M. J. Grote and T. Huckle, Parallel Preconditioning with Sparse Approximate Inverses, SIAM Journal on Scientific Computing, 18 (1997), pp. 838–853.
- [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]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]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]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]J. A. Loe and R. B. Morgan, Toward efficient polynomial preconditioning for GMRES, Numerical Linear Algebra with Applications, 29 (2022), p. e2427.DOI
- [29]Z. Lu, A sparse approximate inverse for triangular matrices based on Jacobi iteration, 2021, https://arxiv.org/abs/2106.12836.
- [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]S. MacLachlan and Y. Saad, Greedy Coarsening Strategies for Nonsymmetric Problems, SIAM Journal on Scientific Computing, 29 (2007), pp. 2115–2143.DOI
- [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]T. Manteuffel and B. S. Southworth, Convergence in Norm of Nonsymmetric Algebraic Multigrid, SIAM Journal on Scientific Computing, 41 (2019), pp. S269–S296.
- [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]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]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]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]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]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]Y. Saad, ILUM: A Multi-Elimination ILU Preconditioner for General Sparse Matrices, SIAM Journal on Scientific Computing, 17 (1996), pp. 830–847.DOI
- [41]Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, 2nd ed., 2003.DOI
- [42]Y. Saad, Multilevel ILU With Reorderings for Diagonal Dominance, SIAM Journal on Scientific Computing, 27 (2005), pp. 1032–1057.DOI
- [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]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]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]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]L. N. Trefethen and M. Embree, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton University Press, Princeton, 2005.
- [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]P. S. Vassilevski, Multilevel Block Factorization Preconditioners: Matrix-based Analysis and Algorithms for Solving Finite Element Equations, Springer, New York, 2008.
- [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]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