Auxiliary Storage Methods for Solving Finite Element Systems

In this paper we consider the direct solution of the system of linear equations Ax = b, where A is a large, sparse, symmetric and positive definite matrix. This system is solved using the Cholesky method by factoring A into RT R, where R is an upper triangular matrix, and then solving RT y = b and Rx = y. We are particularly interested in the case where A is so large that auxiliary storage must be used to store the Cholesky factor R. The approach we use, which fully exploits the sparsity of A, is based on partitioning the given system into subsystems, each of which is sufficiently small that it can be processed in a relatively small amount of main memory. We give a detailed analysis of the input/output (I/O) traffic generated when our method is applied to a model n by n grid problem. The grid is partitioned using an incomplete nested dissection, which is a minor modification of the standard nested dissection ordering. Our analysis shows that if we have O (n²) main memory, then the total I/O traffic is O (n² n). This result implies that the O (n³) numerical computations dominate the I/O traffic. A widely used method for solving such large linear systems is the band method, in which zeros outside the band of A are exploited. The I/O traffic and arithmetic operations in this case are given by O (n³) and O (n⁴), respectively. We also consider an improvement for our basic strategy which reduces the I/O traffic to the extent that it is dominated by writing the Cholesky factor alone. This enhancement reduces the I/O traffic associated with storing intermediate results from O (n² n) to O (n² n). Numerical experiments are also provided to illustrate the performance of our algorithms.