
HP Labs Technical Reports
Click here for full text:
Efficient Methods for OutofCore Sparse Cholesky Factorization
Rothberg, Edward; Schreiber, Robert
HPL98114
Keyword(s): sparse matrix; memory hierarchy; Cholesky factorization
Abstract: We consider the problems of sparse Cholesky factorization with limited main memory. The goal is to efficiently factor matrices whose Cholesky factors essentially fill the available disk storage, using very little memory (as little as 16 Mbytes). This would enable very large industrial problems to be solved with workstations of very modest cost. We consider three candidate algorithms. Each is based on a partitioning of the matrix into panels. The first is a robust, outofcore multifrontal method that keeps the factor, the stack, and the large frontal matrices on disk. The others are leftlooking methods. We find that straightforward implementations of all of them suffer from excessive disk I/O for large problems that arise in interiorpoint algorithms for linear programming. We introduce several improvements to these simple outofcore methods, and find that a leftlooking method that nevertheless uses the multifrontal algorithm for portions of the matrix (subtrees of the supernodal elimination tree whose multifrontal stack fits in memory) is very effective. With 32 Mbytes of main memory, it achieves over 77 percent of its incore performance on all but one of our twelve test matrices (67 percent in that one case), even though the size of the factor is, in all cases, hundreds of millions or even billions of bytes
14 Pages
Back to Index
