Matrixmultiplikation

• Multiplikation von Matrizen:
  • mathematische Definition von C = A * B
    • 
  • zur einfachen Verarbeitung eigene Klasse Matrix
    • 
  • Implementierung der Routine matmult über drei verschachtelte for-Schleifen
  • Anzahl der Operationen bei 2x2-Matrizen:
    • 8 Multiplikationen
    • 4 Additionen
• Beobachtung von Strassen [1]:
  • Betrachte 2x2-Matrizen
    • 
  • Berechnung der c_ij durch geschickte Kombination von Zwischenergebnissen m_i
    • 
  • Anzahl der Operationen:
    • 7 Multiplikationen
    • 18 Additionen
  • Hoffnung: besser, da Multiplikationen "wichtiger" als Additionen
  • inzwischen Verbesserung mit weniger Additionen [2]
• Rekursion im Strassen-Algorithmus:
  • Zerlegung der Matrizen in 2x2 Blöcke
    • 
  • a_ij, b_ij, c_ij jetzt Teilmatrizen der Dimension n/2
  • Berechnung des Produkts mit gleichen Formeln wie oben
  • Produkte der Teilmatrizen rekursiv mit gleichem Verfahren
  • ständiges Halbieren nur möglich, wenn Matrixdimension = Zweierpotenz
  • Abhilfen
    • Matrix mit Nullen erweitern
    • "ungerade" Zeilen/Spalten extra behandeln
• Strassen-Verfahren im Beispiel:
  • Ausgangsmatrizen
    • 
  • Berechnung von m1
    • 
  • Rekursion für das Teilprodukt
    • 
  • Rückkehr aus Rekursion liefert
    • 
  • analog für m2 .. m7 und Gesamtprodukt C