A survey of direct methods for sparse linear systems. (23rd May 2016)

• Record Type: Journal Article
• Authors: Davis, Timothy A.; Rajamanickam, Sivasankaran; Sid-Lakhdar, Wissam M.
• Is Part Of: Acta numerica. Volume 25(2016)
• Page Start: 383
• Page End: 566
• Publication Date: 2016-05-23
• Subjects: Numerical analysis -- Periodicals; 518
• DOI: 10.1017/S0962492916000076
• Languages: English
• ISSNs: 0962-4929

Abstract

Abstract : Wilkinson defined a sparse matrix as one with enough zeros that it pays to take advantage of them. 1 This informal yet practical definition captures the essence of the goal of direct methods for solving sparse matrix problems. They exploit the sparsity of a matrix to solve problems economically: much faster and using far less memory than if all the entries of a matrix were stored and took part in explicit computations. These methods form the backbone of a wide range of problems in computational science. A glimpse of the breadth of applications relying on sparse solvers can be seen in the origins of matrices in published matrix benchmark collections (Duff and Reid1979 a, Duff, Grimes and Lewis1989 a, Davis and Hu2011 ). The goal of this survey article is to impart a working knowledge of the underlying theory and practice of sparse direct methods for solving linear systems and least-squares problems, and to provide an overview of the algorithms, data structures, and software available to solve these problems, so that the reader can both understand the methods and know how best to use them.