next up previous contents
Next: 5.4.4 Parallel algorithms Up: 5.4 Gauß-Seidel iteration Previous: 5.4.2 Data flow of   Contents


5.4.3 Red-Black-Gauß-Seidel iteration

To get rid of the unfavorable properties with respect to the data flow we have to split the subscripts of the vector into (at least) two adjoint subsets  $ \omega_{\mathrm{red}}$ und  $ \omega_{\mathrm{black}}$ so that $ K_{i,j}\equiv 0\;\forall i\neq j \in \omega_{\mathrm{red}}$ (resp.  $ \omega_{\mathrm{black}}$) holds, i.e., there is no coupling between elements of the subsets.
Now, we reformulate the update step in Alg. 5.7 into
\begin{algorithmus} % latex2html id marker 17021 [H] \caption{Update step in Red... ...u}_{\mathrm{black}}^{k-1} \right) \\ \end{array} \end{array}$\end{algorithmus}
The proper data flow is presented in Fig. 5.3.

Figure 5.3: Data flow in Red-Black-Gauß-Seidel forward iteration
\begin{figure}\unitlength0.035\textwidth \mbox{}\hfill \begin{picture}(15,11) %... ...-1} \in \omega_{\mathrm{red}}$}} % \par\end{picture}\hfill\mbox{} \end{figure}

Because of the decoupling property within the subsets of ''red'' and ''black'' data, Alg. 5.8 can be parallelized. This pointwise red/black splitting can be applied to a 5-point-stencil discretization in 2D and also to a 7-point stencil discretization in 3D.

For the target of parallelization a block version of the iteration above is recommended. The blocks should be chosen in such a way that the update of blocks of one color requires no communication. This yields to a checkerboard coloring of the unit square coinciding with the adjoint data distribution in 4.3.2 (again, 2 colors are sufficient if a 5-point-stencil is used).

next up previous contents
Next: 5.4.4 Parallel algorithms Up: 5.4 Gauß-Seidel iteration Previous: 5.4.2 Data flow of   Contents
Gundolf Haase 2000-03-20