An Application of Generalized Tree Pebbling to Sparse Matrix Factorization
Joseph W. H. Liu · SIAM Journal on Algebraic and Discrete Methods · 1987
A generalized version of the pebble game for trees is described. It is motivated by the study of out-of-core methods for the Cholesky factorization of sparse matrices. A solution to the generalized pebbling problem will give an equivalent ordering of the sparse matrix, so that the reordered matrix requires the minimum amount of in-core storage for its out-of-core factorization using the scheme in [12]. An efficient algorithm is presented to determine such an optimal solution.