The Domain Decomposition solver or preconditioner is a memory-efficient iterative algorithm for large problems where other methods are infeasible. The basic idea of the iterative (spatial) domain decomposition is as follows.

Consider an elliptic PDE over a domain D and a partition {Di} such that

Instead of solving the PDE on the entire D at once, the algorithm solves a number of subdomain problems for each subdomain Di. If the subdomain Di is adjacent to a boundary, its boundary conditions are used. On the interfaces between subdomains, certain natural transmission conditions arise. It is known (Ref. 21) that the solution to the set of subdomain problems is equivalent to the original problem formulated over D. The solution can be found by iteratively solving each subdomain problem with all other domains fixed until the convergence criteria is met. This principle is used in domain decomposition methods.

One class of methods is the overlapping Schwarz method, where the partition {Di} grows such that each subdomain overlaps its neighboring domains. The size of the overlap is an important parameter that partly determines the convergence rate of the method. An optional coarse grid problem can also be solved that improves the convergence rate of the method. The coarse grid problem, which is solved on the entire D, gives an estimate of the solution on the fine grid on D. The convergence rate of the method depends on the ratio between the size of the coarse grid mesh elements and the physical size of the overlap on the fine grid.

The domain decomposition method can be used to control the memory consumption. This is achieved in two ways. The total amount of data needed to solve the subdomain problems is usually less than the data needed to solve the entire problem on the domain D. It is also possible to run the domain decomposition solver in a mode where the data used by each subdomain problem is computed on the fly. This results in a significant memory reduction and allows the solution of larger problems without the need to store the data in virtual memory at the price of reduced performance compared to keeping all data in physical memory. This method is useful when the problem would use virtual memory otherwise.

There is a choice between four overlapping Schwarz methods: the additive, multiplicative, hybrid, and symmetric Schwarz methods. The additive method solves all subdomain problems and the coarse grid problem at once before updating the solutions. The hybrid method updates the solution when the coarse grid problem is solved and then solves the remaining problems, updates the solution, and solves the coarse grid problem a second time. These methods can solve all the subdomain problems in parallel when running in distributed mode. The multiplicative method solves each subdomain problem in sequence. The symmetric method also solves the subdomain problems in sequence, but in a symmetric way. In these cases not all problems can be solved in parallel when running in distributed mode, but using coloring techniques it is still possible to achieve parallel speedup. In general the multiplicative and symmetric methods converge faster than the additive and hybrid methods, while the additive and hybrid methods can result in better speedup.