Q:Strassenalgorithmus f. Matrizenmultiplikation
Markus Heck
Warum programmierst Du nicht in Fortran 90, die ja schon die
Funktion MATMUL besitzt. Matmul multipliziert zwei Matrizen, falls
die mathematische Bedingung(Dimensionen muessen gleich sein)
erfuellt ist.
Weiterhin ist in Fortran 90 ja auch das Anlegen von dynamischen
Feldern kein Problem.
Wie es jetzt allerdings mit der Zeitkomplexitaet aussieht, weiss
ich nicht.
Hoffe, geholfen zu haben
Markus
Jahn Rentmeister
: Hallo...
: Warum programmierst Du nicht in Fortran 90, die ja schon die
: Funktion MATMUL besitzt. Matmul multipliziert zwei Matrizen, falls
: die mathematische Bedingung(Dimensionen muessen gleich sein)
: erfuellt ist.
Moechtest du mit diesem Vorschlag andeuten, dass ich ein bereits bestehendes
Programm, das ich noch dazu nicht selbst geschrieben habe, nach Fortran 90
portieren soll, um dann dort eine Matrizenmultiplikationsroutine zu
verwenden, die aller Wahrscheinlichkeit nach dieselbe Komplexitaet hat wie
die unter C verwendete, obwohl die Reduktion der Komplexitaet der einzige
Grund ist, weshalb Hand an den Code zu legen mir vergoennt ist? Um es anders
zu formulieren: Mein Problem ist nicht, zwei Matrizen zu multiplizieren,
vielmehr geluestet es mich, dies mit einem geringerem als dem fuer diese
Operation ueblicherweise in Kauf genommenen Aufwand ausfuehren zu koennen.
Darum programmiere ich nicht in Fortran 90. (Und, weil wir kein Fortran 90
hier haben und ich sowieso nur Fortran 77 kann.)
(Wenn ich mir die Sprache aussuchen koennte, wuerde ich eh' in Ada
programmieren, siehe .sig)
: Weiterhin ist in Fortran 90 ja auch das Anlegen von dynamischen
: Feldern kein Problem.
Mir fallen auf Anhieb noch einige Sprachen mehr ein, in denen das auch kein
Problem ist.
In der Hoffnung, geklaert zu haben
Jahn Rentmeister
--
An Ada-bigot is a bigot, too. But unlike most other bigots, he's right.
Johannes Abt
die nicht 2^n mal 2^n sind:
Angenommen, ich habe habe zwei 3x3-Matrizen:
a b c j k l
d e f m n o
g h i p q r
Dann fasse ich die als 2x2-Matrizen auf:
S c V l
T U W X
mit S = (a b), V = (j k)
T = /d e\ U = /f\ W = /m n\ X = /o\
\f h/ \i/ \p q/ \r/
Und siehe da... man kann Strassen auch hier anwenden.
Aehnlich duerfte es auch fuer andere Matrizen funktionieren.
Eine 4x4-Matrix fasst man ja uebrigens auch als 2x2-Matrix, bestehend
aus 2x2-Untermatrizen auf.
Wenn man dann eine Matrix von, angenommen, 13x13 hat, ist es recht
unguenstig, sie in vier kleinere Matrizen von 6x6, 6x7, 7x7 und 7x6
zu unterteilen und dann konsequenterweise noch z.B. die 6x6-Matrix
in vier 3x3-Matrizen zu zerlegen.
Besser duerfte sein (dieser und obiger Absatz ohne Garantie!), wenn
Du eine n mal n-Matrix in vier Matrizen mit m x m, m x o, o x m, o x o
unterteilst, wobei m die groesstmoegliche Zweiterpotenz < n sein muss.
Dann hast Du in vielen Faellen weniger Sonderfaelle (und wahrscheinlich
auch Multiplikationen).
Fuer obiges Beispiel heisst das: Die 13x13-Matrix sollte in
8x8, 8x5, 5x8 und 5x5-Matrizen geteilt werden. Die 5x5 wird in
4x4, 4x1, 1x4 und 1x1 unterteilt werden. (Auch hier geht der Strassen!)
Beim Implementieren im guten(?), alten "C" wuensche ich viel Spass.
Ciao,
Johannes Abt
P.S. Ich kenne keinen Grund, sich bei der Verwendung vom Strassenschen
Verfahren auf quadratische Matrizen zu beschraenken.
Johannes Abt
>Zu dem Problem der Strassen-Multiplikation mit Matrizen,
>die nicht 2^n mal 2^n sind:
>Angenommen, ich habe habe zwei 3x3-Matrizen:
>a b c j k l
>d e f m n o
>g h i p q r
>Dann fasse ich die als 2x2-Matrizen auf:
>S c V l
>T U W X
>mit S = (a b), V = (j k)
> T = /d e\ U = /f\ W = /m n\ X = /o\
> \f h/ \i/ \p q/ \r/
Sorry, hier ist ein Fehler!
Richtig ist naemlich die Unterteilung:
a b|c j k|l
d e|f m n|o
---+- ---+-
g h|i p q|r
Das ergibt folgende 2x2-Matrizen:
S T V W
U i X r
mit U = (g h), X = (p q)
S = /a b\ T = /c\ V = /j k\ W = /l\
\d e/ \f/ \m n/ \o/
Jetzt MUSS es stimmen!
Servus,
Johannes Abt