6.3.1 Parallelization by means of cyclic reduction

Next: 6.4 FFT Up: 6.3 Gauß elimination of Previous: 6.3 Gauß elimination of Contents

6.3.1 Parallelization by means of cyclic reduction

Cyclic reduction :
Rearranging the equations and unknowns in such a manner that several unknowns can be eliminated at the same time, i.e., in parallel.

Basic idea of rearrangement for unknowns

Eliminate all

with $i \mod 2 = 1$ from the system :

$\begin{displaymath} \begin{array}{ccccccccccccc} b_1 x_1 &+& c_1 x_2 &&&&&&&& &=... ... &=& f_6 \\ &&&&&&&& a_6 x_6 &+& b_7 x_7 &=& f_7 \end{array}\end{displaymath}$

$\Longrightarrow$ $\begin{displaymath}\begin{array}[t]{ccccccc} \widetilde{b} \makebox[0pt]{}_2 x_... ...t]{}_6 x_6 &=& \widetilde{f} \makebox[0pt]{}_3 \\ \end{array}\end{displaymath}$

Eliminate all

with $i \mod 4 = 2$ $\Longrightarrow$ $\widehat{b} \makebox[0pt]{}_4 x_4 = \widehat{f} \makebox[0pt]{}_4$

Generally : $\fbox{\begin{minipage}[t]{0.6\textwidth} Elimination sequence : $2^{k-1} \le n <... ...qquad Eliminate all $x_i$ with $i \mod 2^{j+1} = 2^j$\\ END DO \end{minipage}}$

**Figure 6.6:** Matrix and elimination tree after rearranging by cyclic reduction. The $\bigcirc$ -entries denote additional fill-ins.
$\begin{figure}\unitlength0.048\textwidth \mbox{}\hfill \begin{picture}(20.5,11.... ...} \put(18.85,5.7){\vector(-1,-2){1.7}} \end{picture}\hfill\mbox{} \end{figure}$

The elimination tree and the cyclic reduction presented in Fig. 6.6

requires twice as much arithmetic as the normal Gauß elimination, but
It can be parallelized.
A sequential rearrangement to reduce the fill-in has no meaning at all for the parallel run.

Remark : There exists no special concept for the parallelization of direct solvers for sparse matrices !

Next: 6.4 FFT Up: 6.3 Gauß elimination of Previous: 6.3 Gauß elimination of Contents

Gundolf Haase 2000-03-20