When the dimensionality of solving a problem for a linear system AX = B exceeds the internal memory of a computer, it needs to be partitioned so that part can be brought into memory and the remainder can stay in external storage until required. When matrix A is sparse, the dimensionality of the problem may increase even further, and additional effort must be applied to store and efficiently access the elements of the matrix. Since input/output (I/O) requests to external storage are two orders of magnitude slower than requests to main memory, reduction of the penalty of disk I/O is absolutely necessary.
Meshar, Irony, and Toledo claim the first out-of-core sparse symmetric-indefinite matrix factorization algorithm to be fully described in the open literature. They also claim that it is the first left-looking method to be fully described. It has very low disk I/O traffic, supporting high computation speeds. The method is direct, and more robust than iterative methods. It is out-of-core, meaning that the triangular factors in sparse matrix management are kept on disk, avoiding the need for extra memory.
The paper is fairly long (26 pages), but it is thorough and documents its claims well. After the introductory section, the development follows logically. The second section provides the background for sparse factorizations, and for the data structures that need to be constructed and used. Left-looking factorization is discussed in the third section. This section is important, in that it amplifies one of the main claims of the paper. The fourth section describes pivot admissibility and search, needed for reducing the sparse matrix. The out-of-core factorization algorithm itself is the topic of the fifth section. The last section presents a lengthy performance evaluation of the method compared to other software packages (TAUCS, multi-frontal massively parallel sparse direct solver (MUMPS), and parallel sparse direct linear solver (PARDISO)). The matrices selected for testing approximated real data and problems. This is a seminal paper, which should garner plenty of attention in the future.