Preconditioning Sparse Matrices with Alternating and Multiplicative Operator Splittings

We present an algebraic framework for operator splitting preconditioners for general sparse matrices. The framework leads to four different approaches: two with alternating splittings and two with a multiplicative ansatz. The ansatz generalizes ADI and ILU methods to multiple factors and to a more general factor form. The factors may be computed directly from the matrix coefficients or adaptively by incomplete sparse inversions. The special case of tridiagonal splittings is examined in more detail. We decompose the adjacency graph of the sparse matrix into multiple (almost) disjoint linear forests, and each linear forest (a union of disjoint paths) leads to a tridiagonal splitting. We obtain specialized variants of the four general approaches. Parallel implementations for all steps are provided on a GPU. We demonstrate the effectiveness and efficiency of these preconditioners combined with GMRES on various matrices.