Algebraic Multigrid for Eigenproblems in Industrial Applications of Big Data and Engineering

Abstract

More and more data are generated and gathered by computational simulations, network evaluations, and sensor usage in industrial applications and many other methods. To make the most out of the collected data, these should be examined in search of (hidden) patterns or any other predictive information. This analysis gives rise to sparse linear systems and the need to calculate the smallest eigensolutions of them. <br /> To evaluate these data, matrices via Graph Laplacian or adjacency graphs are defined and the corresponding eigenproblems need to be solved. These matrices mainly have a sparse pattern. However, a few rows do not fit in this pattern. They are connected to more data points. This inhomogeneous pattern is difficult for most linear solvers. This also holds for classical Algebraic Multigrid (AMG), although it should generally be well-suited for these systems. It should be promising as it has excellent scaling properties and is only relying on algebraic information. <br /> AMG, similar to other iterative linear solvers, is a two-phase algorithm. At first, a setup is constructed. This is then used for the solution. In this thesis, we are modifying both phases of the AMG solver in order to apply it to data science problems. <br /> We are introducing a new approach for the setup of AMG that can especially handle the matrix inhomogeneities. Based on this, we will develop an approach to solve (modified) eigenproblems by exploiting the AMG hierarchy for problems as they arise in data analysis. <br /> We demonstrate the applicability of these both methods with various examples. In the first instance, we take the Poisson problem to show the effect of algorithmic variations we implemented. The setup approach is additionally evaluated for petroleum reservoir simulations and different Graph Laplacians. We use the eigensolution calculation also for Graph Laplacians. However, we additionally improve the solution for very ill-conditioned problems from structural mechanics.

Durch Computersimulationen, Auswertung von Netzwerken oder Sensordaten in industriellen Produktionen und vielen weiteren Optionen erzeugen wir immer mehr Daten. Nach Möglichkeit sollten diese Daten ausgewertet werden um Rückschlüsse auf (versteckte) Ähnlichkeiten oder andere weiterverwendbaren Informationen zu erhalten. Bei dieser Analyse ergeben sich große, dünn-besetzte lineare Gleichungssysteme und die Notwendigkeit die kleinsten Eigenlösungen zu bestimmen. <br /> Um die Daten auszuwerten werden aus diesen Matrizen als Graph Laplaces oder Adjazenzgraphen berechnet. Diese werden dann benutzt um die zugehörigen linearen Gleichungssysteme oder Eigenwertprobleme zu lösen. Die entstanden Matrizen haben ein mehrheitlich dünnes Besetzungsmuster. Jedoch fallen einzelne Zeilen aus diesem Muster heraus, weil es einige Datenpunkte gibt, die mehr Verknüpfungen zu anderen Datenpunkten haben. Aus dieser inhomogenen Besetzungstruktur ergeben sich Schwierigkeiten für den linearen Löser. Dies gilt auch für Algebraische Mehrgitter (AMG), welches grundsätzlich als linearer Löser für diese Matrizen einsetzbar ist. AMG verspricht ein idealer linearer Löser zu sein, da dieser über gute Skalierungseigenschaften verfügt und rein algebraisch verwendbar ist. <br /> Wie sehr viele iterative Löser ist auch AMG zweiphasig aufgebaut. Zunächst wird ein Setup konstruiert. Basierend auf diesem wird die Lösung dann iteriert. In der vorliegenden Arbeit werden wir beide Phasen modifizieren um eine bessere Anwendbarkeit für die Datenprobleme zu erreichen. <br /> Zunächst führen wir eine neue Setup-Strategie für AMG ein um besser mit den Matrixinhomogenitäten umgehen zu können. Basierend darauf etablieren wir eine Lösungsphase, die es ermöglicht (generalisierte) Eigenprobleme zu lösen. Bei der Lösung werden wir die im Setup erzeugte AMG Hierarchie mehrfach wieder verwenden. <br /> An Hand verschiedener Beispiele zeigen wir die Anwendbarkeit beider Methoden. Zunächst evaluieren wir diverse algorithmische Variationen am bekannten Poisson Problem. Die Setup-Strategie ist zusätzlich für Ölreservoirsimulationen und verschiedene Graph Laplace ausgewertet. Die Eigenwertberechnung wenden wir ebenfalls auf Graph Laplace an. Außerdem verbessern wir mit Eigenvektoren die Lösbarkeit von schlecht konditionierten Problemen aus der Strukturmechanik.