Automatic solver control for linear equation systems

Abstract

Das Ziel dieser Arbeit war es, eine automatische Steuerung für Gleichungslöser von linearen Gleichungssystemen zu entwickeln, die dem Anwender möglichst alle Entscheidungen bei der Lösung eines linearen Gleichungssystem abnehmen kann. Es soll, wenn möglich, den richtigen Gleichungslösertyp für eine Matrix auswählen, sowie eine geeignete Vorkonditionierung vornehmen.<br />Falls der gewählte Löser nicht zum Ziel führt, sollten noch andere Lösungsvarianten ausgenutzt werden.<br />Der erste Teil der Arbeit beschäftigt sich mit dem notwendigen mathematischen Hintergrund von Matrizen.<br />Außerdem werden die Lösungsalgorithmen von CG, BICGstab und GMRES erklärt und auch einige Vorkonditionierungsmethoden erläutert (Jacobi, unvollständige LR-Zerlegung und unvollständige Cholesky-Zerlegung). Um diese Algorithmen zu testen, wurden verschiedene Software Pakete, die eben diese anbieten, analysiert (Trilinos, PETSc, ITL, QQQ und Hypre), damit ein Pool an Gleichungslösern zur Verfügung gestellt werden kann. Um eine automatische Steuerung zu realisieren, braucht das Programm gewisse Matrixeigenschaften, auf denen die Entscheidungen fußen können.<br />Dazu wurde ein Analysetool entwickelt, das eine Matrix analysiert und verschiedene wichtige Matrixeigenschaften zurückliefert (Bsp.: Symmetrie, Definitheit). Der Hauptteil der Arbeit beschäftigt sich mit dem Test verschiedener Matrizen, um zu sehen, welche Matrixeigenschaften als Entscheidungskriterien verwendet werden können.<br />Aufgrund dieser Matrixeigenschaften wurden dann die Entscheidungen, die eine automatische Steuerung trifft, abgestimmt. Der letzte Teil der Arbeit zeigt das entwickelte Modul angewendet auf die gezeigten Testmatrizen, sowie den Lösungsstatus, und zugehörigen Residuen.<br />

This work describes the development of an automatic solver control for linear equations systems which was designed to help a user to find the optimal solver for a given matrix problem. The used solver algorithms were CG, BICGstab and GMRES, with the preconditioners Jacobi, incomplete LU factorization and incomplete Cholesky factorization. Several solver packages available on the market were tested for their performance (Trilinos, PETSc, QQQ, Hypre and ITL). In order for the automatic solver control to be able to make decisions, it needs to know several properties of a given matrix. For that reason an analyzing tool was developed. The main part of this work consists of a description of the testing of the different solver packages to find out how the various solvers perform and which matrix properties may have an influence on their performance. This testing helped in the adjustment of the decision criteria for the automatic solver control. The last part of this work describes the performance of the automatic solver control which was developed.