High-Performance Out-of-Core Sparse LU Factorization.
John R. Gilbert, Sivan Toledo · 1999
We present an out-of-core sparse nonsymmetric LU-factorization algorithm with partial pivoting. We have implemented the algorithm and our experiments show that it can easily factor matrices whose factors are larger than main memory at rates comparable to those of an in-core solver. The algorithm is novel in several respects, including the use of panels that are larger than memory and the use of a priority queue of updates. 1 Introduction. We present an algorithm for out-of-core sparse LU factorization with partial pivoting. A user may fail to solve a large linear system because a solver breaks down numerically, runs for too long, or runs out of memory. Although most of the research in high-performance scientific computing has focused on reducing running times by exploiting parallelism and locality, many users' failure to solve large systems stems from running out of memory. Our algorithm allows users to factor matrices that are larger than main memory and whose factors are larger than...