|
==== Domain decomposition algorithm ====
Unfortunately, for technical reason it is usually not possible to split our grid of 64 points (a 64×64 system of linear equations) into two grids of 32 points (two 32×6432 systems of linear equations) and obtain an answer to the 64×64 system. Instead, the following algorithm is what actually happens:
:1) Begin with an approximate solution of the 64×64 system.
:2) From the 64×64 system, create two 32×6432 systems to improve the approximate solution.
:3) Solve the two 32×6432 systems.
:4) Put the two 32×6432 solutions "together" to improve the approximate solution to the 64×64 system.
:5) If the solution isn't very good yet, repeat from 2.
There are two ways in which this can be better than solving the base 64×64 system. First, if the number of repetitions of the algorithm is small, solving two 32×6432 systems may be more efficient than solving a 64×64 system. Second, the two 32×6432 systems need not be solved on the same computer, so this algorithm can be run in ''parallel'' to use the power of multiple computers.
In fact, solving two 32×6432 systems instead of a 64×64 system on a single computer (without using parallelism) is unlikely to be efficient. However, if we use more than two subdomains, the picture can change. For instance, we could use four 3216×3216 problems, and there's a chance that solving these will be better than solving a single 64×64 problem even if the ___domain decomposition algorithm needs to iterate a few times.
== A technical example ==
| 