Detailansicht
Reduced nested dissection for fill reducing node orderings
Wolfgang Ost
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Physik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Computational Science
Betreuer*in
Monika Henzinger
Mitbetreuer*in
Christian Schulz
DOI
10.25365/thesis.58691
URN
urn:nbn:at:at-ubw:1-15558.21519.918313-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Bei der Faktorisierung von dünn besetzten Matrizen entstehen oft neue Nicht-Nullen. Diese neuen Elemente werden als Fill-In bezeichnet. Ist der Fill-In groß, kann die Faktorisierung im Hinblick auf Speicherbedarf und Laufzeit teuer werden. Eine Permutation der Matrix kann den Fill-In reduzieren und die Faktorisierung ermöglichen. Das Problem, eine Permutation zu finden, die den Fill-In minimiert, wird üblicherweise mit einem graphtheoretischen Ansatz gelöst. Wir entwickeln einen Algorithmus auf der Basis von Nested Dissection, genannt Reduced Nested Dissection. Mit Hilfe von Reduktionsregeln verkleinern wir die Graphen und verringern damit die Zeit, die benötigt wird, um Trenner zu finden. Damit wird der Nested Dissection Algorithmus signifikant beschleunigt. Wir evaluieren Reduced Nested Dissection anhand von sozialen Netzwerken und ähnlichen Graphen. Mit unseren Reduktionen verringert sich die Anzahl an Nicht-Nullen in den Matrixfaktoren um 2.5% und die Anzahl an Operationen in der Faktorisierung um 5%. Die Laufzeit verbessert sich im Schnitt um 45%, mit einer maximalen Verbesserung von 95.6%. Weiterhin führen wir einen Algorithmus für das Fill-In Problem ein, der auf Clustering von Graphen aufbaut. Das Ziel ist, Permutationen in geringerer Zeit als mit Reduced Nested Dissection zu erhalten. Dieser Algorithmus führt zu Permutationen mit Anzahl an Nicht-Nullen und Operationen, die um Größenordnungen über Ergebnissen von Nested Dissection liegen. Er ist nu rwenig schneller als Reduced Nested Dissection.
Abstract
(Englisch)
When factorizing sparse matrices, non-zeros can be introduced. These non-zeros are called fill-in. If the fill-in is large, factorization can become prohibitively expensive in terms of storage and computation time. A permutation of a matrix can reduce the fill-in and make factorization feasible. The minimum fill-in problem is to find a permutation that minimizes the fill-in. It is commonly solved using a graph representation of the matrix. We introduce reduction rules for the minimum fill-in problem and apply them in a nested dissection algorithm we call reduced nested dissection. Reducing the graphs reduces the time to compute node separators, which speeds up the nested dissection algorithm. We evaluate the performance of reduced nested dissection on a set of social networks, citation networks and web graphs. Our reductions initially reduce the graphs to approximately half their size. They improve the number of non-zeros by 2.5% and the operation count of factorization by 5% over nested dissection without reductions. The running time is reduced by 45% on average, with the best improvement at 95.6%. We also introduce an algorithm for the minimum fill-in problem based on graph clustering, intended to allow for faster computation of node orderings compared to nested dissection. Orderings from this algorithm lead to orders of magnitudes more non-zeros compared to nested dissection, and the running time is reduced only slightly over reduced nested dissection.
Schlagwörter
Schlagwörter
(Englisch)
nested dissection fill-in sparse matrix reduction rules
Schlagwörter
(Deutsch)
Nested Dissection Fill-In Algorithmus
Autor*innen
Wolfgang Ost
Haupttitel (Englisch)
Reduced nested dissection for fill reducing node orderings
Paralleltitel (Deutsch)
Reduced Nested Dissection für fill-in-reduzierende Ordnungen
Publikationsjahr
2019
Umfangsangabe
x, 67 Seiten : Diagramme
Sprache
Englisch
Beurteiler*in
Monika Henzinger
Klassifikationen
31 Mathematik > 31.99 Mathematik: Sonstiges ,
54 Informatik > 54.10 Theoretische Informatik
AC Nummer
AC15557448
Utheses ID
51825
Studienkennzahl
UA | 066 | 910 | |