Efficient solution of large sparse linear systems in modern hardware

Abstract

The solution of large-scale sparse linear systems arises in numerous scientific and engineering problems. Typical examples involve study of many real world multi-physics problems and the analysis of electric power systems. The latter involve key functions such as contingency, power flow and state estimation whose analysis amounts at solving linear systems with thousands or millions of equations. As a result, efficient and accurate solution of such systems is of paramount importance. The methods for solving sparse systems are distinguished in two categories, direct and iterative. Direct methods are robust but require large amounts of memory, as the size of the problem grows. On the other hand, iterative methods provide better performance but may exhibit numerical problems. In addition, continuous advances in computer hardware and computational infrastructures imposes new challenges and opportunities. GPUs, multi-core CPUs, late memory and storage technologies (flash and phase change memories) introduce new capabilities to optimizing sparse solvers. This work presents a comprehensive study of the performance of some, state of the art, sparse direct and iterative solvers on modern computer infrastructure and aims to identify the limits of each method on different computing platforms. We evaluated two direct solvers in different hardware configurations, examining their strengths and weaknesses both in main memory (in-core) and secondary memory (out-of-core) execution in a series of representative matrices from multi-physics and electric grid problems. Also, we provide a comparison with an iterative method, utilizing a general purpose preconditioner, implemented both on a GPU and a multi-core processor. Based on the evaluation results, we observe that direct solvers can be as efficient as their iterative counterparts if proper memory optimizations are applied. In addition, we demonstrate that GPUs can be utilized as efficient computational platforms for tackling the analysis of electric power systems. © 2015 IEEE.