Berechnungsaufwand fuer spaerlich besetzte Matrize

Wissenschaft Mathematik
1

Guten Tag,
ich arbeite zur Zeit an einer Arbeit ueber Modellreduktionsverfahren von flexiblen Mehrkoerpersystemen und moechte einen Rechenzeitvergleich machen.

Ich hoffe es hat jemand eine Antwort auf die folgenden Frage (eine Referenz zur Antwort waere gut)

Rechenzeitaufwand fuer eine Matrizenmultiplikation mit spaerlich besetzten Matrizen.
Fuer voll besetzte Matrizen ist der Aufwand o(n^2.376) bzw. o(n^3) fuer den naiven Algorithmus. Kennt jemand entsprechende Werte fuer spaerlich besetzte Matrizen?

Vielen Dank im Voraus
Mark

2

Hallo,

Rechenzeitaufwand fuer eine Matrizenmultiplikation mit
spaerlich besetzten Matrizen.
Fuer voll besetzte Matrizen ist der Aufwand o(n^2.376) bzw.
o(n^3) fuer den naiven Algorithmus. Kennt jemand entsprechende
Werte fuer spaerlich besetzte Matrizen?

Das hängt natürlich von der Anzahl der nicht-0-Elemente ab, aber hier gibt es z.B. eine Abhandlung dazu: http://portal.acm.org/citation.cfm?id=1077464.1077466

Grüße,
Moritz