Klammerung von Matrixprodukt < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:15 Fr 30.11.2007 | | Autor: | Rinho |
Guten Tag!
Ich habe vor mir ein Matrixprodukt aus neun Matrizen, und suche einen Algorithmus, der mir angibt, wie ich dieses Matrixprodukt optimal klammern kann, d.h., so dass ich möglichst wenige Multiplikationen durchführen muss.
Hat jemand diesbezüglich eine Idee?
Vielen Dank
Robert
|
|
| |
|
Hallo,
ich hatte eben einen längeren Text geschrieben, bis mir ein Licht aufging:
Wenn es ganz allgemeine Matrizen sind, dann kommst du immer auf 8 Multiplikationen, egal, wie du es drehst und wendest...
Du kannst höchstens die Multiplikation etwas vereinfachen, indem du iterativ von links nach rechts paarweise klammerst, bis alles in Klammern steht. Dann werden die Ausdrücke nicht so hässlich (falls du symbolisch rechnest oder die Werte groß werden):
$(((A*B)*(C*D))*((E*F)*(G*H)))*I$
Wenn du einfach von links nach rechts multiplizierst, dann hast du links eine immer hässlichere Matrix.
Die Anzahl der Multiplikationen bleibt aber gleich.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:43 Fr 30.11.2007 | | Autor: | Rinho |
Hallo!
Das war mir schon klar, es geht aber nicht darum..
Ich will die Anzahl der einzelnen Multiplikationen von Matrixelementen minimieren. Bspw. wenn du eine (p x q) und eine (q x r)-Matrix miteinander multiplizierst, erhält man p*q*r Multiplikationen.
Es geht also um die Anzahl aller Multiplikationen von jeweils 2 Matrixelementen miteinander.
|
|
|
| |
|
Hallo,
das wäre ja auch zu einfach gewesen...
Ich habe mir so meine Gedanken gemacht und denke, es wird wohl das beste sein, zuerst die größeren Multiplikationen zu klammern und dann die immer einfacheren. Dann tragen die größeren Matrizen nicht so häufig zu den Produkten der Form, die du angeführt hast, bei.
Am einfachsten ist es, wenn man die Maße der Matrizen links (Zeilen) und rechts (Spalten) schreibt, z.B. 3 A 9. Dann braucht man nur die größten Werte zuerst einzuklammern.
Am umfangreicheren Beispiel: Wir haben 9 Matrizen mit größen bis zu 15 Reihen. Wir schreiben das Produkt inkl. der Maße auf:
8 A 2 B 14 C 9 D 2 E 6 F 5 G 15 H 7 I 10
Nun klammern wir die Matrizenpaare mit den größten Werten ein, die nicht direkt nebeneinander stehen:
8 A 2 (B 14 C) 9 D 2 (E 6 F) 5 (G 15 H) 7 I 10
Dann folgen die nächstkleineren Werte:
8 A 2 ((B 14 C) 9 D) 2 (E 6 F) 5 ((G 15 H) 7 I) 10
usw.
8 (A 2 ((B 14 C) 9 D)) 2 ((E 6 F) 5 ((G 15 H) 7 I)) 10
Ohne die Zahlen steht dort jetzt:
(A ((B C) D)) ((E F) ((G H) I))
So komme ich auf 1515 Multiplikationen
Bei einer Klammerung von links nach rechts komme ich auf 3712, bei einer von rechts nach links auf 4280 Multiplikationen. Ist zwar kein Beweis, aber es scheint zumindest eine gute Heuristik zu sein.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:48 So 02.12.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
