From linear algebraic systems to elimination graphs and harmonic functions

Simple item page
dc.contributor.advisorLiesen, Jörgen
dc.contributor.authorLuce, Roberten
dc.contributor.grantorTechnische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaftenen
dc.contributor.refereeLiesen, Jörgen
dc.contributor.refereeNabben, Reinharden
dc.contributor.refereeKressner, Danielen
dc.contributor.submitterLuce, Roberten
dc.date.accepted2014-11-27
dc.date.accessioned2015-11-20T23:59:24Z
dc.date.available2014-12-04T12:00:00Z
dc.date.issued2014-12-04
dc.date.submitted2014-01-12
dc.description.abstractIn 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.de
dc.description.abstractIn 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.en
dc.identifier.uriurn:nbn:de:kobv:83-opus4-59342
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/4561
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-4264
dc.languageEnglishen
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc518 Numerische Analysisen
dc.subject.otherNumerische Analysisde
dc.subject.otherharmonische Funktionde
dc.subject.otherNumerical analysisen
dc.subject.otherharmonic functionen
dc.titleFrom linear algebraic systems to elimination graphs and harmonic functionsen
dc.title.translatedVon Linearen Gleichungssystemen zu Eliminationsgraphen und Harmonischen Funktionende
dc.typeDoctoral Thesisen
dc.type.versionpublishedVersionen
tub.accessrights.dnbfree*
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.identifier.opus45934
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
luce_robert.pdf
Size:
5.35 MB
Format:
Adobe Portable Document Format
Download

Collections

Publications