Efficient Methods for Out-of-Core Sparse Cholesky Factorization

Rothberg, Edward ; Schreiber, Robert

HP Development Company

关键词: sparse matrix;    memory hierarchy;    Cholesky factorization;   

RP-ID  :  HPL-98-114

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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, out-of-core multifrontal method that keeps the factor, the stack, and the large frontal matrices on disk. The others are left-looking methods. We find that straightforward implementations of all of them suffer from excessive disk I/O for large problems that arise in interior-point algorithms for linear programming. We introduce several improvements to these simple out-of-core methods, and find that a left-looking 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 in-core 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