The Domain Decomposition (Schwarz) and
Domain Decomposition (Schur) solvers or preconditioners are memory-efficient iterative algorithms for large problems where other methods are infeasible. The basic idea of an iterative (spatial) domain decomposition is as follows.
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. 27) 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.
Another class of methods is the Schur complement methods where the partitions of
D are nonoverlapping and separated by a boundary domain
S. If the solution to the boundary domain
S is known, the solution for all domains are trivially computed by inverting the local system matrices of each domain. The solution to the boundary domain is computed by inverting the Schur complement matrix. Because the Schur complement matrix in general is dense, an approximate method is used to compute the inverse. One such method is to use a Schwarz method as a preconditioner for the solution of the Schur complement system. The local systems that corresponds to the subdomain problems in the overlapping Schwarz method can either be inverted in full by using the Localized Schur solver or approximately inverted by using the Sparse Localized Schur solver that filters small entries in the local matrix. See also
Ref. 28 and
Ref. 29.
You can choose from an additive Schur ordering or a
multiplicative Schur ordering. These ordering options determine which corresponding Schwarz algorithm (see
The Overlapping Schwarz Method above) to use for solving the Schur complement system.
A variation of the Schur method is obtained by imposing absorbing boundary conditions on the interior boundaries between subdomains. The boundary problem consists of finding artificial boundary sources to impose on each nonoverlapping domain. If the boundary sources are known, the solution is computed by solving each subdomain problem separately (see Ref. 30). The advantage of this approach over the standard Schur method is that the boundary problem is not dense and can be solved with a Krylov solver without explicitly assembling the boundary matrix, resulting in a significantly lower memory use. On the other hand, the iterative solution of the boundary problem may be computationally expensive, as it requires inverting the local system matrices of all domains at each iteration.
