Strassenalgorithmus zur Matrixmultiplikation |
21.10.2007, 11:48 | Teslarule | Auf diesen Beitrag antworten » | ||
Strassenalgorithmus zur Matrixmultiplikation Ich habe vor ca. 13 Tagen ein Numerik- Projekt von der TU aufbekommen, dass ich bis Mittwoch nächste Woche ausarbeiten muss. Das Thema ist "schnelle" Matrix- Matrixmultiplikation. Es sind jeweils 5 Bereiche auszuarbeiten, wovon ich Nr. 2,3,4 schon habe. Zu Nr. 1 hätte ich eine Frage und bei Nr.5 komme ich überhaupt nicht weiter! Ich hoffe, es kann mir jemand helfen, wär wirklich super! Also hier die Themen: Gegeben ist der Strassen-Alg. de.wikipedia.org/wiki/Strassen-Algorithmus Nun ist bei Nr.1 verlangt, dass man sich von der Richtigkeit des Strassen-Alg überzeugen soll, was auch nicht weiter schwer ist (einfach geschickt einsetzen, und überprüfen ob das richtige rauskommt). Doch hier kommt mein Problem: "Beweisen Sie die Komplexität (O(n^log(7) zur Basis 2)! Wie stell ich das an? Ich hab nirgendswo gefunden, wie man einen Beweis zur Komplexität eines Alg. führt (auch Literatur nicht :/). Hat jemand eine Idee, wie ich die Komplexität des Strassen- Alg beweisen kann? Weil ich finde keinen Ansatz! Wie bereits gesagt, habe ich Nr. 2,3,4 fertig. (Programmieraufgaben in C, C++ und Matlab, also Implementierung, Laufzeitverhalten, Abbruchbed., etc.) Bei Nr.5 (wo ich nicht weiterkomme) ist folgendes gefragt. "Überlegen Sie sich einen Alg., der in ähnlicher Weise (dh rekrusiv!) die normalisierte LU- Zerlegung einer Matrix berechnet. Geben Sie die Komplexität an! Leider habe ich keine Idee, wie ich einen neuen Alg ansetzen soll. Alg., die bereits mehr oder weniger bekannt sind darf ich nicht verwenden. Hab schon fast das ganze Internet abgesucht nach einem ähnlichen Alg, hatte aber bisher keinen Erfolg. Deshalb hoffe ich, dass vielleicht hier jemand schon bereits einen kennt! Danke im Voraus für jede Antwort! GGLG Teslarule PS: habe mein Problem nur bei Matheplanet erörtert, weil ihr seids die besten . |
||||
21.10.2007, 12:08 | kiste | Auf diesen Beitrag antworten » | ||
RE: Strassenalgorithmus zur Matrixmultiplikation
PS: sry für OT aber fand das zu genial, wenn schon lügen dann aber auch schön offensichtlich |
||||
21.10.2007, 12:15 | therisen | Auf diesen Beitrag antworten » | ||
RE: Strassenalgorithmus zur Matrixmultiplikation
Lügner. http://www.matheplanet.com/matheplanet/n...php?topic=89086 |
||||
21.10.2007, 12:22 | Teslarule | Auf diesen Beitrag antworten » | ||
LOL, ich dachte die gehören eh zusammen, weil warum hätte ich bei matheboard wohl geschrieben "... matheplanet...". Nach der Anzahl meiner Posts kann man vielleicht feststellen, dass ich ziemlich anfängermäßig unterwegs bin was Foren angeht.! Und außerdem bestätigt es mich, da "theresien" eh in matheplanet sowie auch mathebaord ist! Hoffe dennoch auf Abhilfe! Gruß EDIT: nach google.mail suche wurde ich sowohl auf matheboard als auch auf matheplant verlinkt.... Dachte das sei dasselbe |
||||
22.10.2007, 12:52 | Dual Space | Auf diesen Beitrag antworten » | ||
RE: Strassenalgorithmus zur Matrixmultiplikation Da der Post bei matheplanet zeitiger erfolgte als bei uns, sollte die Frage vorerst auch nur dort bearbeitet werden, um Helferressourcen zu schonen. *geschlossen* |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|