Strassen-Algorithmus/2x2/Aufgabe

Es seien ${}2\times 2$-Matrizen ${}A={\begin{pmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{pmatrix}}$ und ${}B={\begin{pmatrix}b_{11}&b_{12}\\b_{21}&b_{22}\end{pmatrix}}$ gegeben. Das Produkt ${}A\cdot B$ ergibt sich mit der üblichen Multiplikationsregel „Zeile x Spalte“, bei der man insgesamt ${}8$ Multiplikationen im Körper ${}K$ ausführen muss. Wir beschreiben, wie man diese Matrixmultiplikation mit nur ${}7$ Multiplikationen (aber mit mehr Additionen) durchführen kann. Wir setzen

${}m_{1}={\left(a_{11}+a_{22}\right)}\cdot {\left(b_{11}+b_{22}\right)}\,,$

${}m_{2}={\left(a_{21}+a_{22}\right)}\cdot b_{11}\,,$

${}m_{3}=a_{11}\cdot {\left(b_{12}-b_{22}\right)}\,,$

${}m_{4}=a_{22}\cdot {\left(b_{21}-b_{11}\right)}\,,$

${}m_{5}={\left(a_{11}+a_{12}\right)}\cdot b_{22}\,,$

${}m_{6}={\left(a_{21}-a_{11}\right)}\cdot {\left(b_{11}+b_{12}\right)}\,,$

${}m_{7}={\left(a_{12}-a_{22}\right)}\cdot {\left(b_{21}+b_{22}\right)}\,.$

Zeige, dass für die Koeffizienten der Produktmatrix

${}AB=C={\begin{pmatrix}c_{11}&c_{12}\\c_{21}&c_{22}\end{pmatrix}}\,$

die Gleichungen

${}c_{11}=m_{1}+m_{4}-m_{5}+m_{7}\,,$

${}c_{12}=m_{3}+m_{5}\,,$

${}c_{21}=m_{2}+m_{4}\,,$

${}c_{22}=m_{1}-m_{2}+m_{3}+m_{6}\,,$

gelten.

Zur Lösung, Alternative Lösung erstellen