3.5 Operation auf Vektoren und Matrizen
Am Beispiel der Matrizenrechnung soll gezeigt werden, wie Operationen auf Vektoren und Matrizen mit for-Schleifen realisiert werden können. Es werden Algorithmen für das Skalarprodukt, für die Addition und für die Multiplikation von Matrizen besprochen. Die Matrizen werden durch verschachtelte Listen repräsentiert. Wie eine Matrix transponiert wird, soll in Aufgabe 9 gelöst werden. Außerdem sollen schon erste Laufzeitanalysen durchgeführt werden. Unter Laufzeit (engl. runtime) versteht man in der Informatik die Zeit, die ein Algorithmus für seine Ausführung benötigt. Wie die Laufzeit gemessen werden kann, wird in Abschnitt 3.9.1 ausführlich besprochen. Damit keine bestimmten, hardwareabhängigen Laufzeiten betrachtet werden müssen, wird eine abstrakte Zeiteinheit eingeführt, die die Zeit in der Anzahl der elementaren Rechenoperationen misst. Elementare Rechenoperationen sind die Addition und die Multiplikation.
3.5.1 Skalarprodukt
Das Skalarprodukt ist durch folgende Rechenvorschrift definiert:
Es benötigt n Multiplikationen und n – 1 Additionen. Die gesamte Anzahl der mathematischen Operationen bezeichnet man als Aufwand:
Ein einfaches Beispiel zeigt die Durchführung der Rechnung:
Mit Listing 3.11 können Sie das Skalarprodukt berechnen. In den Zeilen 02 und 03 können Sie andere Vektoren eintragen.
01 #11_skalarprodukt.py
02 a=[1,2,3]
03 b=[3,2,1]
04 n=len(a) #Anzahl der Elemente
05 c=0
06 for i in range(n):
07 c = c + a[i]*b[i]
08 #Ausgabe
09 print(a)
10 print(b)
11 print("Skalarprodukt:",c)
Listing 3.11 Berechnung des Skalarprodukts
Ausgabe
[1, 2, 3]
[3, 2, 1]
Skalarprodukt: 10
Analyse
In den Zeilen 02 und 03 werden die beiden Zeilenvektoren a und b als Listen definiert.
In Zeile 04 ermittelt die eingebaute Python-Funktion die Anzahl der Listenelemente.
In Zeile 07 berechnet der Summenalgorithmus das Skalarprodukt. Es werden zwei Rechenoperationen durchgeführt: Addition und Multiplikation. Für n-Elemente müssen n Multiplikationen und n – 1 Additionen durchgeführt werden, also insgesamt 2n – 1 Operationen. Wenn man für jede Operation jeweils 1 ns annimmt, beträgt die Laufzeit bei drei Schleifendurchläufen 3 ns + 2ns = 5 ns. Die Laufzeit t steigt proportional zu der Anzahl n der Schleifendurchläufe: t = c ⋅ n. Die Konstante c ist abhängig von der Hardware. Für ein gewähltes n0 und die zugehörige Laufzeit t0 kann sie einfach mit c = t0 / n0 vom Programm berechnet werden.
3.5.2 Addition von Matrizen
Die Summe aus zwei Matrizen wird berechnet, indem man einzelne Elemente der Matrizen komponentenweise addiert:
Die Addition von zwei 3×3-Matrizen benötigt neun Additionsoperationen. Allgemein gilt für die Addition von zwei n×n-Matrizen: Der Additionsalgorithmus verlangt n2 Additionsoperationen. Der Aufwand beträgt also
Rechenschritte.
Der Algorithmus für die Addition von zwei n×n-Matrizen besteht aus zwei ineinander verschachtelten for-Schleifen (siehe Listing 3.12):
01 #12_summe_matrix.py
02 a=[[1,2,3],
03 [4,5,6],
04 [7,8,9]]
05 b=[[9,8,7],
06 [6,5,4],
07 [3,2,1]]
08 n=len(a) #Anzahl der Zeilen
09 #Leere (n,n) - Liste erzeugen
10 c=[[0]*n for i in range(n)]
11 for i in range(n): #Zeilen
12 for j in range(n):#Spalten
13 c[i][j]=a[i][j] + b[i][j]
14 #Ausgabe
15 print("Matrix A\n",a)
16 print("Matrix b\n",b)
17 print("Summe\n",c)
Listing 3.12 Addition von zwei Matrizen
Ausgabe
Matrix A
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Matrix b
[[9, 8, 7], [6, 5, 4], [3, 2, 1]]
Summe
[[10, 10, 10], [10, 10, 10], [10, 10, 10]]
Analyse
In den Zeilen 02 bis 07 werden die quadratischen Matrizen a und b als verschachtelte Listen definiert. Zu beachten ist, dass diese Listendefinition mit zwei eckigen Klammern beginnen und auch enden muss.
In Zeile 08 ermittelt die eingebaute Python-Funktion len(a) die Anzahl der Zeilen.
Das Konstrukt in Zeile 10 wird als Listenabstraktion (engl. list comprehension) bezeichnet. Innerhalb der Listendefinition erzeugt eine for-Schleife die leere Liste c.
In den zwei verschachtelten for-Schleifen (Zeilen 11 bis 13) wird die Summe der Matrizen a und b berechnet. Der Index i der äußeren Schleife durchläuft die Zeilen der Matrix, und der Index j der inneren Schleife durchläuft die Spalten der Matrix. In Zeile 13 wird die Summe komponentenweise berechnet. Die innere Schleife wird neunmal (3 ⋅ 3 = 9) durchlaufen. Wenn man für eine Addition eine Rechenzeit von 1 ns annimmt, beträgt die Laufzeit 9 ns. Bei zwei ineinander verschachtelten Schleifen steigt die Laufzeit t quadratisch mit der Anzahl der inneren Schleifendurchläufe: t = c ⋅ n2. Listing 3.21 berechnet für die Addition von zwei n×n-Matrizen die Laufzeiten als Funktion der Eingabelänge n (Anzahl der Zeilen) und stellt sie grafisch als Funktionsplot dar. Wie die Konstante c ermittelt wird, zeige ich Ihnen auch in Listing 3.21 (Zeile 23).
3.5.3 Multiplikation von Matrizen
Die Multiplikation von Matrizen kommt in Kapitel 13, »Ausgleichsrechnungen«, vor. Sie wird für zwei n×n-Matrizen wie folgt durchgeführt:
Zwei 2×2-Matrizen werden wie folgt multipliziert:
Es werden acht Multiplikationen und vier Additionen benötigt. Es ist leicht zu erkennen, dass der Rechenaufwand stark ansteigt, wenn die Gestalt der Matrix auf eine n×n-Matrix vergrößert wird.
Am Beispiel einer 3×3-Matrix soll gezeigt werden, wie die Matrizenmultiplikation praktisch durchgeführt wird:
Hier werden 27 Multiplikationen und 18 Additionen benötigt. Allgemein gilt für die Multiplikation von zwei n×n-Matrizen: Es werden n ⋅ n2 Multiplikationen und n2(n – 1) Additionen benötigt. Der Aufwand beträgt also
Rechenschritte.
Der Algorithmus für die Berechnung des Matrixprodukts besteht aus drei ineinander verschachtelten for-Schleifen.
Hier geht es zunächst nur um die prinzipielle Arbeitsweise einer dreifach verschachtelten for-Schleife. Listing 3.13 benutzt Listen für die Implementierung der Matrizen.
Die Berechnung des Matrixprodukts mit Listen ist nicht besonders effektiv. In Abschnitt 4.1 werden dazu NumPy-Arrays benutzt.
01 #13_produkt_matrix.py
02 a=[[1,2,3],
03 [4,5,6],
04 [7,8,9]]
05 b=[[9,8,7],
06 [6,5,4],
07 [3,2,1]]
08 n=len(a) #Anzahl der Zeilen
09 c=[[0]*n for i in range(n)]
10 for i in range(n): #Zeilen
11 for j in range(n): #Spalten
12 for k in range(n):
13 c[i][j]=c[i][j] + a[i][k]*b[k][j]
14 #Ausgabe
15 print("Matrix A")
16 for i in range(n):print(a[i])
17 print("Matrix B")
18 for i in range(n):print(b[i])
19 print("Matrixprodukt")
20 for i in range(n):print(c[i])
Listing 3.13 Matrixprodukt
Ausgabe
Matrix A
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
Matrix B
[9, 8, 7]
[6, 5, 4]
[3, 2, 1]
Matrixprodukt
[30, 24, 18]
[84, 69, 54]
[138, 114, 90]
Analyse
Die Multiplikation der beiden Matrizen a und b erfolgt im Inneren (Zeile 13) der drei ineinander verschachtelten for-Schleifen (Zeilen 10 bis 13).
Die Produktsumme des Matrixprodukts c[i][j] wird mit dem Summenalgorithmus c[i][j]=c[i][j]+a[i][k]*b[k][j] berechnet (Zeile 13).
Die innere Schleife wird 27-mal durchlaufen. Für drei ineinander verschachtelte Schleifen mit jeweils n Iterationen gilt allgemein für die Anzahl der Schleifendurchläufe in der inneren Schleife: n ⋅ n ⋅ n = n3. Es werden n3 Multiplikationen und (n3 – n2) Additionen durchgeführt. Wenn man für eine Multiplikation und für eine Addition jeweils 1 ns annimmt, würde die Rechenzeit 27 ⋅ 1 ns + 18 ⋅ 1 ns = 45 ns betragen. Das klingt nicht dramatisch. Zu bedenken ist allerdings, dass die Rechenzeit kubisch mit der Anzahl der Operationen steigt. Für sehr große n würde selbst der schnellste Rechner an diesem Algorithmus scheitern. Bei drei ineinander verschachtelten Schleifen gilt für die Laufzeit t die vereinfachte Annahme: t = c ⋅ n3.
Volker Strassen fand 1969 einen Algorithmus für die Matrizenmultiplikation, dessen Laufzeit proportional zu n2,807… steigt (log2 ⋅ 7 = 2,807…) [Golub:31]. Mit der Python-Konsole können Sie einen genaueren Wert des Exponenten ausrechnen: