TABLE OF CONTENTS As multiprocessing technology steadily gains ground, new classes of numerical methods that can take better advantage of parallelism are emerging. Among these techniques, domain decomposition methods are undoubtedly the best known and perhaps the most promising for certain types of problems. These methods combine ideas from partial differential equations (PDEs), linear algebra, and mathematical analysis, and techniques from graph theory. This chapter is devoted to decomposition methods, which are based on the general concepts of graph partitionings.
Domain decomposition methods refer to a collection of techniques that revolve around the principle of divide and conquer. Such methods have been primarily developed for solving PDEs over regions in two or three dimensions. However, similar principles have been exploited in other contexts of science and engineering. In fact, one of the earliest practical uses for domain decomposition approaches was in structural engineering, a discipline that is not dominated by PDEs. Although this chapter considers these techniques from a purely linear algebra viewpoint, the basic concepts, as well as the terminology, are introduced from a model PDE.
Consider the problem of solving the Laplace equation on an L-shaped domain ? partitioned as shown in Figure 14.1. Domain decomposition or substructuring methods attempt to solve the problem on the entire domain
from problem solutions on the subdomains ? i. There are several reasons why such techniques can be advantageous. In the case of the above picture, one obvious reason is...
