Diploma Thesis DIP-3267

BibliographySaleh, Ramzy: Implemenierung und Anwendung von Laplacian-Eigenmap Verfahren.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 3267 (2012).
58 pages, german.
CR-SchemaG.1.3 (Numerical Linear Algebra)
G.2.2 (Discrete Mathematics Graph Theory)
Abstract

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.

Full text and
other links
PDF (1889961 Bytes)
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Simulation of Large Systems
Superviser(s)Zimmer, Stefan
Entry dateJune 21, 2012
   Publ. Computer Science