Software for Sparse Gaussian Elimination with Limited Core Storage.
Eisenstat,S C, Martin H. Schultz, Andrew H. Sherman · Defense Technical Information Center (DTIC) · 1978
A variant of Gaussian elimination is presented for solving sparse symmetric systems of linear equations on computers with limited core storage, without the use of auxiliary storage such as disk or tape. The method is based on the somewhat unusual idea of recomputing rather than saving most nonzero entries in the reduced triangular system, thus trading an increase in work for a decrease in storage. For a nine-point problem with the nested dissection ordering on an n x n grid, fewer than (7/2)n-squared nonzeroes must be saved versus approx(-93/12)n-squared(logbase2n) for sparse elimination, while the work required at most doubles. The use of auxiliary storage in sparse elimination is also discussed. (Author)