Reduced nested dissection for fill reducing node orderings

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.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