A synchronization-free incomplete LU factorization for GPUs with level-set analysis

Abstract

Incomplete factorization methods are powerful algebraic preconditioners widely used to accelerate the convergence of linear solvers. The parallelization of ILU methods has been extensively studied, particularly for GPUs, which are ubiquitous parallel computing devices. In recent years, synchronizationfree methods have become the mainstream approach for solving sparse triangular linear systems. Although the sparse triangular solver and ILU factorization are closely related, the application of synchronization-free strategies to ILU factorization has not been explored in the literature to the same extent as the triangular solver. In this work, we present synchronization-free implementations of the ILU-0 preconditioner on GPUs. Specifically, we propose three implementations that vary in how row updates are handled after each coefficient elimination, as well as an additional approach that leverages a prior level-set analysis to optimize the execution schedule decomposition, which computes the full factorization of A, ILU only performs an incomplete factorization by discarding certain fill-ins that would otherwise appear in L and U. This approach preserves sparsity in the factors, helping to control memory usage and computational costs. ILU is a widely used algebraic preconditioner and is often chosen when no further information about the problem is available. However, ILU factorizations can be computationally expensive, especially for large sparse matrices, partly because ILU parallelism is limited by serial dependencies in the Gaussian elimination sequence. To address this, various efforts have been made to parallelize the ILU on GPUs, including approaches based on level-set analysis [3], [4], graph-coloring [5], and iterative methods [6], [7].