Adaptive Precision Sparse Matrix–Vector Product and Its Application to Krylov Solvers

.We introduce a mixed precision algorithm for computing sparse matrix-vector products and use it to accelerate the solution of sparse linear systems by iterative methods. Our approach is based on the idea of adapting the precision of each matrix element to their magnitude: we split the elements into buckets and use progressively lower precisions for the buckets of progressively smaller elements. We carry out a rounding error analysis of this algorithm that provides us with an explicit rule to decide which element goes into which bucket and allows us to rigorously control the accuracy of the algorithm. We implement the algorithm on a multicore computer and obtain significant speedups (up to a factor \(7\times\)) with respect to uniform precision algorithms, without loss of accuracy, on a range of sparse matrices from real-life applications. We showcase the effectiveness of our algorithm by plugging it into various Krylov solvers for sparse linear systems and observe that the convergence of the solution is essentially unaffected by the use of adaptive precision.Keywordsmixed precisionadaptive precisionmultiple precisionmatrix–vector productsparse matrixSpMVnumerical linear algebrarounding error analysisfloating-point arithmeticKrylov solverGMRESCGBiCGstabiterative solverlinear systemMSC codes65G5065F0565F0865F5065F10