Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4264
Main Title: From linear algebraic systems to elimination graphs and harmonic functions
Translated Title: Von Linearen Gleichungssystemen zu Eliminationsgraphen und Harmonischen Funktionen
Author(s): Luce, Robert
Advisor(s): Liesen, Jörg
Referee(s): Liesen, Jörg
Nabben, Reinhard
Kressner, Daniel
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: In dieser Dissertation werden Fragestellungen behandelt, die sich aus der Lösung von schwachbesetzten, linearen Gleichungssystemen ergeben. So wird zunächst untersucht, wie das bekannte Minimum-Fill Problem in der schwachbesetzen Cholesky-Faktorisierung mit dem Problem der Minimierung der arithmetischen Operationen zur Berechnung eben dieser zusammenhängt. Hierzu wird eine Klasse von Graphen konstruiert, für welche keine Eliminationsordung für die Faktorisierung existiert, welche für diese beiden Probleme zugleich optimal ist. Weiterhin wird eine Reduktionkette konstruiert, welche zeigt, dass das Minimieren der Arithmetik NP-schwer ist. Während die vorgenannten Untersuchungen dem Umfeld der direkten Lösung von linearen Gleichungssystemen zuzuordnen sind, beschäftigt sich der zweite Teil mit einer Fragestellung, die sich aus der Theorie der iterativen Verfahren zur Lösung solcher Systeme ergibt. Es wird untersucht, welche Verteilungen von Eigenwerten einer Matrix es erlauben, die Rekursionslänge eines verallgemeinerten Arnoldi-Verfahrens zur Konstruktion von Orthogonalbasen von Krylovräumen bezüglich der Matrix zu verkürzen. Dieses Problem läuft auf die Untersuchung von Nullstellen bestimmter komplexer, nicht-analytischer Funktionen hinaus, welche erstaunlicherweise eine enge Verbindung zu sogannnten Gravitationslinsen in der Astrophysik haben.
In this dissertation we study mathematical problems arising in the analysis of certain methods for the solution of sparse, linear algebraic systems of equations. In the first part we investigate the relationship of the minimum fill problem in the sparse Cholesky factorization to the problem of minimizing the number of arithmetic operations in the computation of the Cholesky factor. We construct a class of graphs, parameterized by the number of vertices, for which no elimination ordering in the factorization is optimal for both problems. We further present a reduction chain showing that the minimization of the arithmetic work is NP hard. While these investigations happen in the context of direct methods for the solution of linear systems of equations, the second part of this thesis studies questions originating from the iterative solutions of such systems. In particular, we study the distribution of eigenvalues of matrices that allow to shorten the length of a generalized Arnoldi recurrence for the construction of orthogonal bases for certain sequences of Krylov spaces. As it turns out, this problem can be studied in terms of the set of zeros of certain non-analytic functions from the complex plane to itself. Surprisingly, these functions have a strong connection to so-called gravitational lenses studied in astrophysics.
URI: urn:nbn:de:kobv:83-opus4-59342
http://depositonce.tu-berlin.de/handle/11303/4561
http://dx.doi.org/10.14279/depositonce-4264
Exam Date: 27-Nov-2014
Issue Date: 4-Dec-2014
Date Available: 4-Dec-2014
DDC Class: 518 Numerische Analysis
Subject(s): Numerische Analysis
harmonische Funktion
Numerical analysis
harmonic function
Usage rights: Terms of German Copyright Law
Appears in Collections:Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
luce_robert.pdf5.48 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.