4.3.1.4 Matrix-times-Vector multiplication.

Here, we investigate Matrix-times-Vector multiplication with vectors and matrices of various types. A more abstract presentation of that topic can be found in [Gro94].

1. Type-II matrix $\times$ type-I vector results in a type-II vector.
   Indeed, we achieve from definition (4.1) :

   $${\ensuremath{\color{green}{\sf K}}}\cdot\underline{{\ensuremath{\... ...color{green}{\sf r}}}}_i} \;=\; \underline{{\ensuremath{\color{green}{\sf r}}}}$$ (4.7)

   
   
   The (not necessary) execution of the summation (implying communication) results in a type-I vector.
2. Type-II matrix $\times$ type-II vector needs a conversion of the vector previously to the multiplication in item 1.
3. The operation type-I matrix $\times$ type-I vector cannot be performed with arbitrary type-I matrices  $\color{red}\mathfrak{M}$.
   For a detailed analysis, we study the operation $\underline{{\ensuremath{\color{red}\mathfrak{u}}}}={\ensuremath{\color{red}\mathfrak{M}}}\cdot\underline{{\ensuremath{\color{red}\mathfrak{w}}}}$ on node $n$ in Fig. 4.5. The local multiplication $\underline{{\ensuremath{\color{red}\mathfrak{u}}}}_i={\ensuremath{\color{red}\mathfrak{M}}}_i\cdot\underline{{\ensuremath{\color{red}\mathfrak{w}}}}_i$ should result in a type-I vector  $\underline{{\ensuremath{\color{red}\mathfrak{u}}}}$ at node $n$ in both subdomains. $$\begin{eqnarray*} {\ensuremath{\color{red}\mathfrak{u}}}_2^{[n]} &=& {\ensurema... ...k{M}}}_4^{[n,r]}{\ensuremath{\color{red}\mathfrak{w}}}_4^{[r]} \end{eqnarray*}$$ Terms 4 and 5 of the right hand side in the above equations differ such that processes 2 and 4 achieve different results instead of a unique one. The reason consists in the transport of information via the matrix from a process $a$ to a node belonging additionally to another process $b$.
   Denote by $\omega_i = \{ s : x_i \in \overline{\Omega}_s\}$ the processors a node $i$ belongs to, e.g. in Fig. 4.4, $\omega_n = \{2,4\}$, $\omega_p = \{1,2\}$, $\omega_s = \{2\}$. Then, the transport of information from node $j$ to a node $i$ is only admissible if $\omega_i \subseteq \omega_j$. Representing the matrix entries as directed graph then, e.g., in Fig. 4.4 the entries $q \rightarrow k$, $q \rightarrow n$, $s \rightarrow n$, $s \rightarrow m$, $s \rightarrow p$, $p \rightarrow k$, $n \rightarrow k$, $p \rightarrow n$, $n \rightarrow p$, $\ell \rightarrow k$, $k \rightarrow \ell$ are not admissible. Thus, just a matrix of the shape

   $${\ensuremath{\color{red}\mathfrak{M}}} \;=\; \begin{pmatrix}{\ens... ...color{red}\mathfrak{M}}}\cdot\underline{{\ensuremath{\color{red}\mathfrak{w}}}}$$ (4.8)

   
   
   with block-diagonal matrices ${\ensuremath{\color{red}\mathfrak{M}}}_{I}$, ${\ensuremath{\color{red}\mathfrak{M}}}_{E}$, ${\ensuremath{\color{red}\mathfrak{M}}}_{V}$ omits such forbidden entries. Whereas the block-diagonality of ${\ensuremath{\color{red}\mathfrak{M}}}_{I}$ and the block structure of  ${\ensuremath{\color{red}\mathfrak{M}}}_{IE}$, ${\ensuremath{\color{red}\mathfrak{M}}}_{IV}$ is guaranteed by the data decomposition, for the remaining three matrices the mesh has to fulfill the requirements
   1. No connection between vertices belonging to different sets of subdomains. This guarantees the block-diagonality of  ${\ensuremath{\color{red}\mathfrak{M}}}_{V}$ (often ${\ensuremath{\color{red}\mathfrak{M}}}_{V}$ is a diagonal matrix). No connection between vertices and opposite edges, e.g. in Fig. 4.4, $\ell \not\rightarrow p$. This ensures the admissible structure of  ${\ensuremath{\color{red}\mathfrak{M}}}_{EV}$ (and  ${\ensuremath{\color{red}\mathfrak{M}}}_{VE}$).
   2. No connection between edge nodes belonging to different sets of subdomains. This guarantees the block-diagonality of  ${\ensuremath{\color{red}\mathfrak{M}}}_{E}$.
   Requirement (a) can be easily fulfilled if, at least, one node is located on all edges between two vertices and one node lies in the interior of each subdomain (or has been added therein). A modification of the given mesh generator can also guarantee that requirement 3b is fulfilled, e.g., the edge between nodes $p$ and $n$ is omitted. Fig. 4.6 presents the revised mesh.
   $\bullet$ This strategy can be applied only to triangular or tetrahedral finite elements.
   $\bullet$ In general, rectangular elements do not fulfill condition 3b.

   Figure 4.6: Non-overlapping elements with a revised discretization.

   

4. As stated in the previous point, type-I matrix $\times$ type-II vector cannot be performed with general type-I matrices  $\color{red}\mathfrak{M}$. As result we would expect a type-II vector.
   Assuming that the necessary requirements (a) and (b) are fulfilled by the mesh (see Fig. 4.6) we can focus our interest to the operation $\underline{{\ensuremath{\color{green}{\sf f}}}}_I = {\ensuremath{\color{green}{\sf M}}}_{IC}\cdot\underline{{\ensuremath{\color{green}{\sf r}}}}_C$. Performing this operation locally on processor 4 gives
   $${\ensuremath{\color{green}{\sf f}}}_4^{[r]} \;=\; {\ensuremath{\c... ...M}}}_{IC,4}^{[r,m]}\cdot{\ensuremath{\color{green}{\sf r}}}_4^{[m]} \enspace .$$
   Due to the type-II vector property, we miss in the result the entries ${\ensuremath{\color{red}\mathfrak{M}}}_{IC,2}^{[r,n]}\cdot{\ensuremath{\color{green}{\sf r}}}_2^{[n]}$ and ${\ensuremath{\color{red}\mathfrak{M}}}_{IC,2}^{[r,m]}\cdot{\ensuremath{\color{green}{\sf r}}}_2^{[m]}$. The difference to the previous point is that the transport of information from node $j$ to a node $i$ is permitted only if $\omega_i\supseteq\omega_j$. Thus, just a matrix of the shape

   $${\ensuremath{\color{red}\mathfrak{M}}} \;=\; \begin{pmatrix}{\ens... ...or{red}\mathfrak{M}}}_i\underline{{\ensuremath{\color{green}{\sf r}}}}_i\right)$$ (4.9)

   
   
   with block-diagonale matrices ${\ensuremath{\color{red}\mathfrak{M}}}_{I}$, ${\ensuremath{\color{red}\mathfrak{M}}}_{E}$, ${\ensuremath{\color{red}\mathfrak{M}}}_{V}$ can be used in this type of matrix-by-vector multiplication.

Remark: Items 3 and 4 can be combined under the assumption that ${\ensuremath{\color{red}\mathfrak{M}}}_{V}$, ${\ensuremath{\color{red}\mathfrak{M}}}_{E}$, ${\ensuremath{\color{red}\mathfrak{M}}}_{I}$ are block-diagonale matrices (guaranteed by the mesh in Fig. 4.6). Denote with ${\ensuremath{\color{red}\mathfrak{M}}}_L$, ${\ensuremath{\color{red}\mathfrak{M}}}_U$ and  ${\ensuremath{\color{red}\mathfrak{M}}}_D$ the strictly lower, upper and diagonal part of  $\color{red}\mathfrak{M}$. Then, we can perform the type I matrix-by-vector multiplication for all types of vectors

$$\begin{eqnarray}\underline{{\ensuremath{\color{red}\mathfrak{w}}}... ... \cdot \underline{{\ensuremath{\color{green}{\sf r}}}}\enspace . \end{eqnarray}$$ (4.10a)

Note, that in any case the above multiplications require two type conversions, but the choice of the vectors influences directly the amount of communication needed.

If the Matrix  $\color{red}\mathfrak{M}$ has been factored as $M={\ensuremath{\color{red}\mathfrak{L}}}^{-1}{\ensuremath{\color{red}\mathfrak{U}}}^{-1}$ with the lower and an upper triangular matrices  ${\ensuremath{\color{red}\mathfrak{L}}}^{-1}$ and  ${\ensuremath{\color{red}\mathfrak{U}}}^{-1}$, which fulfill conditions 3 and 4, then we write

$$\begin{eqnarray}\underline{{\ensuremath{\color{red}\mathfrak{w}}}... ...ot\underline{{\ensuremath{\color{red}\mathfrak{u}}}}_i \enspace .\end{eqnarray}$$ (4.11a)

The second case, i.e., $M={\ensuremath{\color{red}\mathfrak{U}}}^{-1}{\ensuremath{\color{red}\mathfrak{L}}}^{-1}$ results in

$$\begin{eqnarray}\underline{{\ensuremath{\color{red}\mathfrak{w}}}... ...cdot\underline{{\ensuremath{\color{red}\mathfrak{u}}}} \enspace .\end{eqnarray}$$ (4.12a)

The equations for the remaining combinations of vector types in (4.12) and (4.13) can be easily derived by type conversion. Here, the number and the kind of type conversion is also determined by the way of factoring the matrix  $\color{red}\mathfrak{M}$.