5.5.2 Parallel ILU-Factorization

The first idea for parallelization of ILU is the simple rewriting of Alg. 5.12 with an accumulated matrix  ${\ensuremath{\color{red}\mathfrak{K}}}$. Naturally, ${\ensuremath{\color{red}\mathfrak{L}}}$ und  $\color{red}\mathfrak{U}$ are also accumulated matrices, however, because of (4.9) and (4.10) we have to fulfill requirements on the mesh 3a and 3b from Sec. 4.3.1.

The redundantly stored matrices ${\ensuremath{\color{red}\mathfrak{K}}}_V$, ${\ensuremath{\color{red}\mathfrak{K}}}_E$, ${\ensuremath{\color{red}\mathfrak{K}}}_E$, ${\ensuremath{\color{red}\mathfrak{K}}}_{EV}$ and  ${\ensuremath{\color{red}\mathfrak{K}}}_{VE}$ will not updated before their (pointwise) factorization so that the matrix accumulation can be performed in the beginning.
In 3D, additional blocks with subscript ''$F$'' have to be taken into account. The proper factorization is similar but some additional conditions on the mesh appear.

Comparing those matrix-times-vector multiplications (4.9) and (4.10) admissible for accumulated matrices within the elimination $\underline{{\ensuremath{\color{red}\mathfrak{w}}}} = {\ensuremath{\color{red}\... ...r{red}\mathfrak{L}}}^{-1} \cdot \underline{{\ensuremath{\color{green}{\sf r}}}}$, one can derive that therein 3 vector type changes are necessary.

The diagonal matrix $R$ including the number of subdomains sharing a node was defined in (4.4).

Improvement : The disadvantage of Alg. 5.15 consists in the fact that always the wrong vector type is available. This leads to the 3 vector type changes including 2 accumulations and means doubling the communication costs per iteration compared to the $\omega$-Jacobi iteration.

$\Longrightarrow$ According to (4.12a), the elimination $\underline{{\ensuremath{\color{red}\mathfrak{w}}}} = {\ensuremath{\color{red}\... ...r{red}\mathfrak{U}}}^{-1} \cdot \underline{{\ensuremath{\color{green}{\sf r}}}}$ would require only one vector type change including one accumulation.

$$\downarrow$$