Implementierung und Anwendung von Laplacian-Eigenmap Verfahren

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.