Cache-aware Sparse Patterns for the Factorized Sparse Approximate Inverse Preconditioner

Conjugate Gradient is a widely used iterative method to solve linear systems 𝐴𝑥 = 𝑏 with matrix 𝐴 being symmetric and positive definite. Part of its effectiveness relies on finding a suitable preconditioner that accelerates its convergence. Factorized Sparse Approximate Inverse (FSAI) preconditioners are a prominent and easily parallelizable option. An essential element of a FSAI preconditioner is the definition of its sparse pattern, which constraints the approximation of the inverse 𝐴 -1 . This definition is generally based on numerical criteria. In this paper we introduce complementary architecture-aware criteria to increase the numerical effectiveness of the preconditioner without incurring in significant performance costs. In particular, we define cache-aware pattern extensions that do not trigger additional cache misses when accessing vector 𝑥 in the 𝑦 = 𝐴𝑥 Sparse Matrix-Vector (SpMV) kernel. As a result, we obtain very significant reductions in terms of average solution time ranging between 12.94% and 22.85% on three different architectures -Intel Skylake, POWER9 and A64FX -over a set of 72 test matrices.