Agnes Scott College

Ruth Gonzalez

Domain Decomposition for Two-Dimensional Elliptic Operators on Vector and Parallel Machines
Rice University, 1986

Abstract

The efficient computation of the solution to self-adjoint elliptic operators is the subject of this dissertation. Discretization of this equation by finite differences or finite elements yields a large, sparse, symmetric system of equations, Ax = b. We use the preconditioned conjugate gradient method with domain decomposition to develop an effective, vectorizable preconditioner which is suitable for solving large two-dimensional problems on vector and parallel machines.

The convergence of the preconditioned conjugate gradient method is determined by the condition number of the matrix M-1A where A and M correspond to the matrix for the discretized differential equation and to the preconditioning matrix, respectively. By appropriately preconditioning the system Ax = b we can significantly reduce the computational effort that is required in solving for x

The basic approach id domain decomposition techniques is to break up the domain of integration into many pieces, solve the appropriate equation on each piece, then somehow construct the global solution from these local solutions. In this dissertation we formulate an effective preconditioner for two-dimensional elliptic partial differential equations using this notion of domain decomposition. We demonstrate that this method is efficient in its vectorized form and present numerical results to support this conclusion.

Conclusions

An efficient solution of the two-dimensional self-adjoint elliptic partial differential equation via domain decomposition using vector or parallel machines has been described in this dissertation. We demonstrated that it works on many kinds of problems including those with non-uniform mesh, variable coefficients, discontinuous coefficients, and rectangular domains. We determined the optimal relationship between the fine mesh which is used to discretize the domain of integration and the number of subdomains. We were able to determine what factors inhibited or enhanced the convergence of this new numerical process. We conclude that standard block methods are better suited for small problems but that this new procedure is ideal for large problems. Finally, it was demonstrated that this method effectively utilizes vector or parallel machines with CRAY-like architecture which are designed to be efficient even for relatively short vector lengths.

One could further study the effect of utilizing additional capabilities of the CRAY-XMP. GATHER/SCATTER hardware could be used to virtually eliminate the data movement problem. One could essentially reduce the computation time by a factor of four my multi-tasking for up to four processors when the number of unknowns is large. The overhead for using the four processors would be minimal since additional data communication would not be necessary. Also, note that this would have absolutely no effect on the convergence of the algorithm since exactly the same calculations would be carried out. These considerations would shift the recommend optimal number of subdomains for a given mesh. All of these modifications would make a practical extension to three-dimensional problems.