The Floating Point Systems array processor AP120B can be used to efficiently solve large systems of linear equations by a sparse Gaussian elimination technique. Bench mark tests show the following results: For LU factorization, the AP120B requires 22 to 35% less CPU time than the IBM 370/168; for forward or back substitution, the AP120B requires 0 to 44% less CPU time. Coding considerations are discussed for the AP120B in sparse elimination.
In many reservoir simulation problems, we seek the solution of a system of nonlinear, parabolic partial differential equations describing multiphase flow. Common approximation techniques used to solve the partial differential equations lead to a sequence of partial differential equations lead to a sequence of linear equations
(1)
where A is a matrix and x and b are vectors.
One effective way to solve Equation (1) is to use Gaussian elimination. Since A is sparse, sparse Gaussian elimination techniques have been developed to solve the equation efficiently.
In a reservoir simulation study Equation (1) is solved repeatedly, sometimes taking as much as 80% of the total computing time. Consequently, there is strong incentive to reduce the cost of solving Equation (1). The purpose of this paper is to show that a sparse elimination technique, when used in conjunction with an array processor, is capable of solving Equation (1) efficiently and economically.
The array processor is a high-performance auxiliary computer that works in parallel with a host computer. Figure 1 illustrates schematically an array processor-host computer combination. The applications processor-host computer combination. The applications program, such as a reservoir simulator, executes in program, such as a reservoir simulator, executes in the host computer. The program may call on the array processor to perform calculations by issuing a processor to perform calculations by issuing a Fortran or Assembler call. At the same time, data are transmitted from the host computer to the array processor via an I/O channel. The array processor, processor via an I/O channel. The array processor, working independently, then calls in the appropriate algorithms to perform the calculations. When these are completed, the results are returned to the host computer via the I/O channel. An interface program, or host operating system driver, provides control of data transfer and synchronization of operations.
A number of array processors have recently appeared on the market. Three that can be attached to large, general-purpose host computers are given in Table 1. The array processor used in this investigation is the Floating Point Systems AP120B with a 333-nanosecond memory of 256K 38-bit floating point words. The host computer is the IBM 370/168.
Several authors have discussed the application of sparse elimination techniques to reservoir simulation. The technique consists of two steps. First, we renumber or reorder the grid to minimize the fill-in during elimination and the number of arithmetic operations involving nonzeroes. Second, we solve the permuted system using Gaussian elimination, storing and operating on only the nonzeroes of A plus the new nonzeroes that occur during elimination.
The renumbering of a grid is accomplished through a suitable numbering scheme, such as the alternate diagonal scheme described in Reference 3; or by using a renumbering algorithm, such as the minimum degree algorithm discussed in Reference 2. Renumbering needs to be done only once for each grid and is best performed by a Fortran program on the host computer. performed by a Fortran program on the host computer. In solving Equation (1) by Gaussian elimination, a series of operations is used to transform A into an upper triangular matrix, U, such that
U × = d (2)
