Diplomarbeit DIP-3267

Bibliograph.
Daten
Saleh, Ramzy: Implemenierung und Anwendung von Laplacian-Eigenmap Verfahren.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Diplomarbeit Nr. 3267 (2012).
58 Seiten, deutsch.
CR-Klassif.G.1.3 (Numerical Linear Algebra)
G.2.2 (Discrete Mathematics Graph Theory)
Kurzfassung

Mit dem Laplacian-Eigenmap-Verfahren kann man auf eine bestimmte Punktmenge im Raum eine Struktur oder eine Ordnung einführen. In dieser Arbeit wurde eine spezielle Ordnung verfolgt, die eine Punktmenge so miteinander ordnet, dass Punkte, die nah beieinander liegen, zusammen gehören. Dieses Vorgehen wird detailliert und anhand vieler Beispiele vorgestellt.

Weiterhin werden Operationen der Matrix-Matrix-Multiplikation als 3D-Koordinaten betrachtet und eine neue Struktur darauf definiert, die Operationen miteinander ordnet, die den gleichen Operanden besitzen. Die Anwendung des Laplacian-Eigenmap-Verfahren auf diesen 3D-Koordinaten und ihre neue Struktur liefert als Ausgabe die Operationen der Matrix-Matrix-Multiplikation in einer für den Cache sehr effizienten Reihenfolge.

Diese erstellte Multiplikationsfolge, die ich Laplace-Folge genannt habe, wird in dieser Arbeit einer vergleichenden Analyse mit 2 anderen, etablierten Verfahren unterzogen. Im Vergleich zu der konservativen Matrix-Matrix-Multiplikation (Zeile aus Matrix A multipliziert mit Spalte aus Matrix B.) führt die erwähnte Multiplikationsfolge zu einer deutlich besseren Cache-Ausnutzung, die einer Cache-Ausnutzung-Kurve wie bei der Peano-Multiplikation-Folge (Beruht auf die Peano-Kurve und bekannt für ihre effiziente Cache-Ausnutzung.) ähnelt und nahekommt, jedoch etwas schlechtere Werte aufweist.

Volltext und
andere Links
PDF (1889961 Bytes)
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Simulation großer Systeme
BetreuerZimmer, Stefan
Eingabedatum21. Juni 2012
   Publ. Institut   Publ. Informatik