Matrix-Multiplikation

Matrix-Multiplikation
Das Produkt einer (` × m)-Matrix A und einer (m × n)-Matrix B ist die
(` × n)-Matrix
m
X
C = AB ,
ci,k =
ai,j bj,k ,
j=1
Matrix-Multiplikation
1-1
Matrix-Multiplikation
Das Produkt einer (` × m)-Matrix A und einer (m × n)-Matrix B ist die
(` × n)-Matrix
m
X
C = AB ,
ci,k =
ai,j bj,k ,
j=1
d.h. zur Definition von ci,k werden die Produkte der Elemente aus Zeile
von A und Spalte k von B summiert:

 

b1,k

 

..

 

.

 






ci,k
bj,k

 =  ai,1 · · · ai,j · · · ai,m  

 

..

 

.
bm,k
Matrix-Multiplikation
i








1-2
Matrix-Multiplikation
Das Produkt einer (` × m)-Matrix A und einer (m × n)-Matrix B ist die
(` × n)-Matrix
m
X
C = AB ,
ci,k =
ai,j bj,k ,
j=1
d.h. zur Definition von ci,k werden die Produkte der Elemente aus Zeile
von A und Spalte k von B summiert:

 

b1,k

 

..

 

.

 






ci,k
bj,k

 =  ai,1 · · · ai,j · · · ai,m  

 

..

 

.
bm,k
i








Man beachte, dass dazu die Spaltenzahl von A mit der Zeilenzahl von B
übereinstimmen muss.
Matrix-Multiplikation
1-3
Die Matrixmultiplikation entspricht der Komposition der linearen
Abbildungen
T : u 7→ v = Bu, S : v 7→ w = Av ,
d.h. C = AB ist die Matrixdarstellung von S ◦ T .
Matrix-Multiplikation
1-4
Die Matrixmultiplikation entspricht der Komposition der linearen
Abbildungen
T : u 7→ v = Bu, S : v 7→ w = Av ,
d.h. C = AB ist die Matrixdarstellung von S ◦ T .
Die Matrix-Multiplikation ist i.a. nicht kommutativ.
Matrix-Multiplikation
1-5
Beweis:
Komposition der durch
wi =
m
X
ai,j vj ,
vj =
j=1
n
X
bj,k uk
k=1
definierten Abbildungen
wi =
XX
j
k


X X

ai,j bj,k uk =
ai,j bj,k  uk
k
j
mit [...] = ci,k den Elementen der Matrix C = AB
Matrix-Multiplikation
2-1
Beispiel:
einige konkrete Matrix-Produkte:


1 3 2
1 10 100 
321
213
132
2 1 3  =
100 10
1
123 312 231
3 2 1
Matrix-Multiplikation
3-1
Beispiel:
einige konkrete Matrix-Produkte:

1 3
1 10 100 
2 1
100 10
1
3 2
 
1
 2  0
3

2
321
213
132
3  =
123 312 231
1


0 −1
−1
=  0 −2 
0 −3
Matrix-Multiplikation
3-2
Beispiel:
einige konkrete Matrix-Produkte:


1 3 2
1 10 100 
321
213
132
2 1 3  =
100 10
1
123 312 231
3 2 1
 


1
0 −1
 2  0 −1
=  0 −2 
3
0 −3
3
3 4
= 25
4
Matrix-Multiplikation
3-3
Beispiel:
einige konkrete Matrix-Produkte:


1 3 2
1 10 100 
2 1 3 
100 10
1
3 2 1
 
1
 2  0 −1
3
3
3 4
4
1 i
1
i 1
i
=
321 213 132
123 312 231


0 −1
=  0 −2 
0 −3
= 25
=
0
2i
Matrix-Multiplikation
3-4
Beispiel:
Berechnung des Produktes C = AB von zwei (2 × 2)-Matrizen A, B in der
üblichen Weise
8 Multiplikationen
V. Strassen: 7 Multiplikationen genügen
[Gaussian elimination is not optimal, Numer. Math. 13 (1969), 357–361]
p1
p2
p3
p4
p5
p6
p7
c1,1
c1,2
c2,1
c2,2
=
=
=
=
=
=
=
=
=
=
=
(a1,2 − a2,2 )(b2,1 + b2,2 )
(a1,1 + a2,2 )(b1,1 + b2,2 )
(a1,1 − a2,1 )(b1,1 + b1,2 )
(a1,1 + a1,2 )b2,2
a1,1 (b1,2 − b2,2 )
a2,2 (b2,1 − b1,1 )
(a2,1 + a2,2 )b1,1
a1,1 b1,1 + a1,2 b2,1
a1,1 b1,2 + a1,2 b2,2
a2,1 b1,1 + a2,2 b2,1
a2,1 b1,2 + a2,2 b2,2
=
=
=
=
p1 + p2 − p4 + p6
p4 + p5
p6 + p7
p2 − p3 + p5 − p7
Matrix-Multiplikation
4-1
Rekursive Anwendung der Konstruktion in Blockform auf Matrizen der
Dimension n = 2k
Reduktion der Multiplikationen von n3 auf O(nlog2 7 )
Matrix-Multiplikation
4-2
Rekursive Anwendung der Konstruktion in Blockform auf Matrizen der
Dimension n = 2k
Reduktion der Multiplikationen von n3 auf O(nlog2 7 )
Verbesserung: O(n2.376... )
[D. Coppersmith, S. Winograd: Matrix Multiplication via arithmetic
progressions, J. Symb. Comp. 9 (1990), 251–280]
Matrix-Multiplikation
4-3
Rekursive Anwendung der Konstruktion in Blockform auf Matrizen der
Dimension n = 2k
Reduktion der Multiplikationen von n3 auf O(nlog2 7 )
Verbesserung: O(n2.376... )
[D. Coppersmith, S. Winograd: Matrix Multiplication via arithmetic
progressions, J. Symb. Comp. 9 (1990), 251–280]
Vermutung: O(n2 ) möglich (optimaler Exponent noch unbekannt)
Matrix-Multiplikation
4-4
Rekursive Anwendung der Konstruktion in Blockform auf Matrizen der
Dimension n = 2k
Reduktion der Multiplikationen von n3 auf O(nlog2 7 )
Verbesserung: O(n2.376... )
[D. Coppersmith, S. Winograd: Matrix Multiplication via arithmetic
progressions, J. Symb. Comp. 9 (1990), 251–280]
Vermutung: O(n2 ) möglich (optimaler Exponent noch unbekannt)
Die Methode hat heute keine praktische Bedeutung mehr, da auf
modernen Computern Multiplikation und Addition fast gleich schnell sind.
Matrix-Multiplikation
4-5
Beispiel:
Bei der Hintereinanderausführung zweier Spiegelungen S1 und S2 an
unterschiedlichen Achsen g1 und g2 ist die Reihenfolge relevant.
g1
g2
2ϑ
g1
ϑ
g2
g1
ϑ 2ϑ
g2
Doppelspiegelung S2 ◦ S1 und Doppelspiegelung S1 ◦ S2
Matrix-Multiplikation
5-1
Beispiel:
Bei der Hintereinanderausführung zweier Spiegelungen S1 und S2 an
unterschiedlichen Achsen g1 und g2 ist die Reihenfolge relevant.
g1
g2
2ϑ
g1
ϑ
g2
g1
ϑ 2ϑ
g2
Doppelspiegelung S2 ◦ S1 und Doppelspiegelung S1 ◦ S2
Drehungen um den doppelten Winkel zwischen den Geraden in
unterschiedliche Richtungen
Matrix-Multiplikation
5-2
wähle g1 als erste Winkelhalbierende und g2 als y -Achse
Matrixdarstellungen der Abbildungen:
0 1
v = S1 u =
u
1 0
Matrix-Multiplikation
5-3
wähle g1 als erste Winkelhalbierende und g2 als y -Achse
Matrixdarstellungen der Abbildungen:
0 1
v = S1 u =
u
1 0
−1 0
v = S2 u =
u
0 1
Matrix-Multiplikation
5-4
wähle g1 als erste Winkelhalbierende und g2 als y -Achse
Matrixdarstellungen der Abbildungen:
0 1
v = S1 u =
u
1 0
−1 0
v = S2 u =
u
0 1
Darstellungen der Doppelspiegelungen:
−1 0
0 1
w = S2 S1 u =
u
0 1
1 0
Matrix-Multiplikation
5-5
wähle g1 als erste Winkelhalbierende und g2 als y -Achse
Matrixdarstellungen der Abbildungen:
0 1
v = S1 u =
u
1 0
−1 0
v = S2 u =
u
0 1
Darstellungen der Doppelspiegelungen:
0 −1
−1 0
0 1
u
w = S2 S1 u =
u=
1
0
0 1
1 0
Matrix-Multiplikation
5-6
wähle g1 als erste Winkelhalbierende und g2 als y -Achse
Matrixdarstellungen der Abbildungen:
0 1
v = S1 u =
u
1 0
−1 0
v = S2 u =
u
0 1
Darstellungen der Doppelspiegelungen:
−1 0
0
w = S2 S1 u =
0 1
1
0 1
−1
w = S1 S2 u =
1 0
0
1
0
0
1
u=
0 −1
1
0
u
u
Matrix-Multiplikation
5-7
wähle g1 als erste Winkelhalbierende und g2 als y -Achse
Matrixdarstellungen der Abbildungen:
0 1
v = S1 u =
u
1 0
−1 0
v = S2 u =
u
0 1
Darstellungen der Doppelspiegelungen:
−1 0
0
w = S2 S1 u =
0 1
1
0 1
−1
w = S1 S2 u =
1 0
0
1
0
0
1
u=
u=
Matrix-Multiplikation
0 −1
1
0
0 1
−1 0
u
u
5-8
wähle g1 als erste Winkelhalbierende und g2 als y -Achse
Matrixdarstellungen der Abbildungen:
0 1
v = S1 u =
u
1 0
−1 0
v = S2 u =
u
0 1
Darstellungen der Doppelspiegelungen:
−1 0
0
w = S2 S1 u =
0 1
1
0 1
−1
w = S1 S2 u =
1 0
0
1
0
0
1
u=
u=
0 −1
1
0
0 1
−1 0
u
u
Drehungen um 90◦ Grad in entgegengesetzte Richtungen
Matrix-Multiplikation
5-9
wähle g1 als erste Winkelhalbierende und g2 als y -Achse
Matrixdarstellungen der Abbildungen:
0 1
v = S1 u =
u
1 0
−1 0
v = S2 u =
u
0 1
Darstellungen der Doppelspiegelungen:
−1 0
0
w = S2 S1 u =
0 1
1
0 1
−1
w = S1 S2 u =
1 0
0
1
0
0
1
u=
u=
0 −1
1
0
0 1
−1 0
u
u
Drehungen um 90◦ Grad in entgegengesetzte Richtungen
Kommutator:
0 1
0 −1
[S1 , S2 ] =
−
−1 0
1
0
Matrix-Multiplikation
5-10
wähle g1 als erste Winkelhalbierende und g2 als y -Achse
Matrixdarstellungen der Abbildungen:
0 1
v = S1 u =
u
1 0
−1 0
v = S2 u =
u
0 1
Darstellungen der Doppelspiegelungen:
−1 0
0
w = S2 S1 u =
0 1
1
0 1
−1
w = S1 S2 u =
1 0
0
1
0
0
1
u=
u=
0 −1
1
0
0 1
−1 0
u
u
Drehungen um 90◦ Grad in entgegengesetzte Richtungen
Kommutator:
0 2
0 1
0 −1
=
[S1 , S2 ] =
−
−2 0
−1 0
1
0
Matrix-Multiplikation
5-11