A tupleware approach to domain decomposition methods

Abstract

Domain decomposition methods are highly parallel methods for solving elliptic partial differential equations. In many domain decomposition variants, the domain is partitioned into a number of (possibly overlapping) subdomains before computation begins. In contrast, the domain reduction method folds the domain into a number of smaller domains covering only a small portion of the entire domain. The solution over the entire domain is recovered by unfolding the solutions on the subdomains and summing them. The cost of the folding and unfolding is negligible. Results are derived measuring how much time and space can be reduced in the problem discretization phase by using these methods. Storage can be reduced by a substantial factor (a factor of eight is constructed for an example in this paper), and discretization time can be reduced by a constant factor or more, depending on the time complexity formula for a given problem. The amount of storage required is substantially less than for traditional domain decomposition implementations, or ones based on standard iterative methods or multigrid (standard or nontelescoping). A highly portable implementation using the Linda system for parallel or distributed programming is discussed. Linda adds a tuple data abstraction to a language, which is used to develop numerical software. © 1991.