Secondary Storage Methods for Solving Symmetric, Positive Definite, Banded Linear Systems.
John Richard Perry · Defense Technical Information Center (DTIC) · 1981
The solution of a linear system of equations Ax=b is often computed using variations of Gaussian elimination. A major problem with these methods is the large storage requirement to compute the factorization of matrices that arise in practice. We focus on the Cholesky method for factoring banded, symmetric, positive definite matrices, which arise in finite-difference and finite-element simulations. We develop and analyze methods for using secondary storage in cases where there is not enough primary memory to compute the band Cholesky factorization. Many computer configurations used for scientific computation allow for control over the parallel execution of I/O and computation. For several of the secondary storage methods, we present storage and I/O schemes that allow I/O to be overlapped with computation. We derive conditions under which the factorization is compute-bound, i.e., all I/O between the initial input and the final output is completely hidden behind concurrent computation. Further, we show that the amount of memory needed to achieve compute-boundedness is independent of the size and bandwidth of the matrix. Thus, for a given processor speed and I/O rate, a constant amount of memory is sufficient to keep the processor busy during the band Cholesky factorization.