High Performance Sparse Iterative Solvers for Heterogeneous Systems: Optimization and Linear Algebra

The thesis is divided into two parts: the first presents the implementation of two optimization algorithms based on the ALP/GraphBLAS library, the second part analyzes the theory and implementation of an Iterative Refinement (IR) technique for solving sparse linear systems at high precision on hardware only supporting low-precision floating point operations. Simulated Annealing-Replica Exchange (SARE) and Simulated Bifurcation (SB) are two physics-inspired general optimization techniques. The first is natu- rally expressed in a Single Program Multiple Data fashion, which naturally maps to a multiprocess implementation. This easily combines with the multithreaded GraphBLAS library to form a hybrid implementation. SB is naturally expressed using GraphBLAS’ linear algebra primitives. Both implementations are evaluated on selected problems of the G-set collec- tion. In a single-threaded setting, these solvers show competitive performance. Furthermore, SARE shows good scalability up to 4 nodes, while SB scales well, quickly reaching the memory bandwidth limit. The novel IR technique shown in this work can be seen as a combination of classical IR methods with an Ozaki scheme. The matrix is decomposed into low-precision parts: all are used to keep a precise estimate of the residual as in a standard Ozaki scheme, while the update direction is computed using a half-precision Conjugate Gradient (CG). We evaluate this IR method on a set of Symmetric Positive Definite sparse matrices with controlled condition numbers and densities. In this setting, the runtime of the IR is similar to some multithreaded CPU implementations of CG working in double precision, while reliably achieving double-precision accuracy on well-conditioned matrices.