Domain decomposition and model integration - Computational River Dynamics - page 331

Figure 8.7 “Red-black” ordering method.
The method consists of two Jacobi steps: black points are updated first, and then the
red points. When the values at black points are updated, only the “old” values at red
points are used, see Eq. (4.219); in the next step, red values are calculated using the
updated black points. This alternate application of the Jacobi method to the two sets
of points produces a method with the same convergence properties as the Gauss-Seidel
method. When applying this “red-black” ordering method on parallel computers, only
the results of the previous step are needed, and thus the computations of new values on
either set of points can be performed in parallel. Communication between processors
working on neighboring blocks takes place twice per iteration step — after each set of
points is updated.
It is not straightforward to extend the TDMA (TriDiagonal-Matrix Algorithm) from
single block to multiple blocks, because it is recursive. This can be demonstrated by
using the 1-D problem shown in Fig. 8.3. If a single block is used for the entire domain,
the boundary-condition information from the ends of the domain is transmitted at once
to the interior through the double sweeps in each iteration step. This results in fast
convergence of iteration. However, if multiple blocks are used for the domain and
a separate TDMA is used in each block, the boundary-condition information at the
ends of the domain is transmitted block by block to the interior; thus, the convergence
speed decreases. To avoid this, one may decompose the computations at each sweep
into multiblocks, and keep the double sweeps over the entire domain.
For a multidimensional problem, the ADI method, which uses alternately the TDMA
in different directions, requires special partition of the solution domain for extension
from single block to multiple blocks. One of the most efficient partitions is shown
in Fig. 8.8. The calculation consists of two steps. In the first step when the implicit
scheme is applied on i -lines and the explicit scheme is on j -lines, the entire domain is
divided into horizontal strips (blocks) that extend along i -lines and end at west and
east boundaries. The TDMA can be used at the strips along i -lines. Similarly, in the
second step when the implicit scheme is applied on j -lines and the explicit scheme is
on i -lines, the entire domain is divided into vertical strips that extend along j -lines and