4.3.1.4 Matrix-mal-Vektor Multiplikation.

Im folgenden sehen wir uns die Matrix-mal-Vektor Multiplikationen von Vektoren und Matrizen der verschiedenen Typen an. Eine andere Darstellung findet man in [Gro94].

1.

 Typ-II Matrix $\times$ Typ-I Vektor ergibt einen Type-II Vektor.
Tatsächlich ergibt sich aus Definition (4.1) :

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

Die Ausführung der Summation (d.h. Kommunikation) führt zu einem Typ-I Vektor.

2.

  Typ-II Matrix $\times$ Typ-II Vektor erfordert eine Vektorkonvertierung bevor obige Multiplikation ausgeführt werden kann.

3.

  Typ-I Matrix $\times$ Typ-I Vektor kann nicht mit beliebigen Typ-I Matrizen  berechnet werden.
Zur genaueren Analyse werfen wir einen Blick auf den Knoten $n$ in Abb. 4.5 und die Operation  $\underline{{\ensuremath{\color{red} \mathfrak{u} } }}={\ensuremath{\color{red} \mathfrak{M} } }\cdot\underline{{\ensuremath{\color{red} \mathfrak{w} } }}$. Die lokale Multiplikation $\underline{{\ensuremath{\color{red} \mathfrak{u} } }}_i={\ensuremath{\color{red} \mathfrak{M} } }_i\cdot\underline{{\ensuremath{\color{red} \mathfrak{w} } }}_i$ sollte als Ergebnis einen Typ-I Vektor  $\underline{{\ensuremath{\color{red} \mathfrak{u} } }}$ im Knoten $n$ hervorbringen.

$$\begin{eqnarray*}{\ensuremath{\color{red} \mathfrak{u} } }_2^{[n]} &=& {\ensurem... ...} }_4^{[n,r]}{\ensuremath{\color{red} \mathfrak{w} } }_4^{[r]} \end{eqnarray*}$$

In obigen Gleichungen unterscheiden sich die Terme 4 und 5 der rechten Seiten, so daß die Prozessoren 2 und 4 anstelle des eindeutigen Resultats zwei verschiedene besitzen. Der Grund dafür liegt im Informationstransport durch die Matrix von einem Prozessor $a$ zu einem Knoten welcher zusätzlich auch noch zu Prozessor $b$ gehört. In anderen Worten - der Transport von Information von einem Knoten $i$ zu einem Knoten $j$ ist nur dann erlaubt, wenn die Menge der Prozessoren, zu denen Knoten $i$ gehört, eine Teilmenge der Prozessoren ist, welche Knoten $j$ besitzen ( $\omega_i \supseteqq \omega_j$). Stellt man die Matrixeinträge als gerichteten Graphen dar, so heißt dies z.B., daß in Abb. 4.5 die Einträge $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$ in der Matrix nicht erwünscht sind.
Somit vermeidet nur eine Matrix der Form

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

mit Blockdiagonalmatrizen ${\ensuremath{\color{red} \mathfrak{M} } }_{I}$, ${\ensuremath{\color{red} \mathfrak{M} } }_{E}$, ${\ensuremath{\color{red} \mathfrak{M} } }_{V}$ solche unerwünschten Einträge. Während die Blockdiagonalstruktur von ${\ensuremath{\color{red} \mathfrak{M} } }_{I}$ durch die Datenaufteilung garantiert ist, muß das FE-Netz für die restlichen Matrizen die folgenden Anforderungen erfüllen :

(a)

 Keine Verbindung zwischen Crosspoints, welche zu verschiedenen Mengen von Teilgebieten gehören.

(b)

  Keine Verbindung zwischen Kanten, welche zu verschiedenen Mengen von Teilgebieten gehören.

Bedingung 3a kann einfach durch dadurch erreicht werden, daß auf jeder Gebietskante mind. ein zusätzlicher Kantenknoten plaziert wird (Achtung bei Verbindung quer durch das Teilgebiet). Ein 2D Netzgenerators für Dreiecke mit linearen Ansatzfunktionen kann leicht so modifiziert werden, daß Bedingung 3b eingehalten wird, z.B. wird die Kante zwischen den Knoten $p$ und $n$ vermieden. Abb. 4.6 zeigt das geänderte Netz.
Diese Vorgehen ist nur bei bestimmten finiten Elementen möglich !
Bei Verwendung von Tetraedern mit linearen Ansatzfunktionen kann Bedingung 3b auch in 3D Netzgeneratoren eingebaut werden.

  

Abbildung 4.6: Nichtüberlappende Elemente mit Diskretisierung bei angepaßtem Netz.

4.

  Wie im vorangegangen Punkt kann Typ-I Matrix $\times$ Typ-II Vektor nicht mit allgemeinen Typ-I Matrizen  durchgeführt werden. Das Ergebnis sollte ein Typ-II Vektor sein.
Nehmen wir an, die (auch hier notwendigen) Bedingungen 3a and 3b seien durch das Netz (Abb. 4.6) erfüllt. Richten wir unsere Aufmerksamkeit auf die Operation $\underline{{\ensuremath{\color{green} {\sf f}} }}_I\,=\,{\ensuremath{\color{red} \mathfrak{M} } }_{IC}\cdot\underline{{\ensuremath{\color{green} {\sf r}} }}_C$. Lokal auf Prozessor 4 ausgeführt liefert

$${\ensuremath{\color{green} {\sf f}} }_4^{[r]} \;=\; {\ensurem... ...\cdot{\ensuremath{\color{green} {\sf r}} }_4^{[m]} \enspace .$$

Wegen der Eigenschaften des Typ-II Vektors  ${\ensuremath{\color{green} {\sf r}} }$ fehlen im Resultat die Teile ${\ensuremath{\color{red} \mathfrak{M} } }_{IC,2}^{[r,n]}\cdot{\ensuremath{\color{green} {\sf r}} }_2^{[n]}$ und ${\ensuremath{\color{red} \mathfrak{M} } }_{IC,2}^{[r,m]}\cdot{\ensuremath{\color{green} {\sf r}} }_2^{[m]}$. Im Unterschied zum vorigen Punkt ist der Transport von Information von Knoten $i$ zu Knoten $j$ nur zulässig, falls die Menge der Prozessoren zu denen $j$ gehört eine Teilmenge der Prozessoren von Knoten $i$ ist ( $\omega_i \subseteqq \omega_j$). In Abb.4.6 sind z.B. $n \rightarrow k$ und $q \rightarrow k$ erlaubt, aber nicht die umgekehrte Richtung. Damit kann nur eine Matrix der Form

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

mit Blockdiagonalmatrizen ${\ensuremath{\color{red} \mathfrak{M} } }_{I}$, ${\ensuremath{\color{red} \mathfrak{M} } }_{E}$, ${\ensuremath{\color{red} \mathfrak{M} } }_{V}$ für diese Art der Matrix-mal-Vektor Multiplikation benutzt werden.

Bemerkung: Die Punkte 3 und 4 können unter der Bedingung, daß ${\ensuremath{\color{red} \mathfrak{M} } }_{V}$, ${\ensuremath{\color{red} \mathfrak{M} } }_{E}$, ${\ensuremath{\color{red} \mathfrak{M} } }_{I}$blockdiagonal sind (durch das Netz in Abb. 4.6 garantiert) kombiniert werden. Bezeichnen ${\ensuremath{\color{red} \mathfrak{M} } }_L$, ${\ensuremath{\color{red} \mathfrak{M} } }_U$ und  ${\ensuremath{\color{red} \mathfrak{M} } }_D$ das streng untere bzw. streng obere Dreiecks und die Diagonale von  , kann die Typ I Matrix-mal-Vektor Operation für alle Vektortypen aufgeschrieben werden.

     

Jede dieser Multiplikationen benötigt genau zwei Vektortypumwandlungen, jedoch beeinflußt die konkrete Wahl der Vektortypen die Anzahl der Kommunikationsschritte.

Die Faktorisierung der Matrix  in eine obere und untere Dreiecksmatrix  ${\ensuremath{\color{red} \mathfrak{L} } }^{-1}$ und  ${\ensuremath{\color{red} \mathfrak{U} } }^{-1}$, die den Bedingungen 3 bzw. 4 genügen müssen, kann auf zwei Weisen geschehen. Zum einem gilt

   

und andererseits

   

Die fehlenden Gleichungen können leicht mittels Typkonvertierung erhalten werden. Bei der Faktorisierung beeinflußt die konkrete Wahl der Vektortypen die Anzahl und Art der der Konvertierungen.