Massive Memory Buys Little Speed for Complete, In-Core Sparse Cholesky Factorizations.

This note is intended to call into question a claim one sometimes hears about the time it takes to compute a complete sparse Cholesky factorization (after a suitable symbolic factorization phase and without using auxiliary memory). The claim is that loop-free code or code that uses a list with one or more addresses or integers for each arithmetic operation runs considerably faster than code with more modest memory requirements, e.g. , memory proportional to the number of nonzeros in the Cholesky factorization. On some commonly used scalar machines (e.g. , various VAX(TM) models and the Sun-3(TM)), one can often come within a factor of two of the optimal floating- point operation rate with a scheme that stores one integer per nonzero in the Cholesky factor.