TU Darmstadt / ULB / TUbiblio

Computational Complexity Theory for Advanced Function Spaces in Analysis

Steinberg, Florian :
Computational Complexity Theory for Advanced Function Spaces in Analysis.
[Online-Edition: http://tuprints.ulb.tu-darmstadt.de/6096]
Technische Universität , Darmstadt
[Dissertation], (2016)

Offizielle URL: http://tuprints.ulb.tu-darmstadt.de/6096

Kurzbeschreibung (Abstract)

This PhD thesis presents progress in the search for a mathematical rigorous framework for efficient numerics of partial differential equations based on a realistic machine model. While the computability theory of continuous structures is well developed and still an active field of research, in most settings it remains unclear what computations should be considered feasible. This problem is tackled within the framework of second-order representations. The name as well as the notion of polynomial-time computability of the framework is inherited from the complexity theory of functionals on the Baire space, also called second-order complexity theory. As model of computation we use oracle Turing machines. Second-order representations offer a great deal of freedom in developing models of computation and a supply of well investigated structures. In particular, there exists an established second-order representation of the set of continuous functions on the unit interval. This representation has been classified as the weakest representation such that evaluation is possible in polynomial time. As a first step we specify the weakest representation of the integrable functions such that integration is polynomial-time computable. This representation turns out to be discontinuous and therefore not suitable. We go on to explore the general restrictions of bounded-time computations on metric spaces within the framework of second-order representations. The notion of metric entropy, originally introduced by Kolmogorov, is used to classify those compact metric spaces that allow for a short representation such that the metric is computable efficiently. To be able to apply the results to spaces of integrable functions we investigate quantitative versions of classification results of their compact subsets called the Arzelà-Ascoli Theorem and the Fréchet-Kolmogorov Theorem. We use the above to propose a family of representations for Lp-spaces. These are shown to be computably equivalent to the standard representations of the same spaces as metric spaces. Furthermore, we prove that the norm can be computed in exponential time. This is also the case for the supremum norm on the continuous functions on the unit interval. A similar family of representations is presented for Sobolev spaces. These representations are investigated in some detail. Several operators on Sobolev spaces are proven to be polynomial-time computable with respect to these representations. For technical reasons only the one-dimensional case is discussed. Finally, we present a result that classifies the computational complexity of the solution operator of the Dirichlet Problem for Poisson’s Equation on the unit disk as that of integrating a continuous function. As a tool for the comparison, polynomial-time Weihrauch reductions are used.

Typ des Eintrags: Dissertation
Erschienen: 2017
Autor(en): Steinberg, Florian
Titel: Computational Complexity Theory for Advanced Function Spaces in Analysis
Sprache: Englisch
Kurzbeschreibung (Abstract):

This PhD thesis presents progress in the search for a mathematical rigorous framework for efficient numerics of partial differential equations based on a realistic machine model. While the computability theory of continuous structures is well developed and still an active field of research, in most settings it remains unclear what computations should be considered feasible. This problem is tackled within the framework of second-order representations. The name as well as the notion of polynomial-time computability of the framework is inherited from the complexity theory of functionals on the Baire space, also called second-order complexity theory. As model of computation we use oracle Turing machines. Second-order representations offer a great deal of freedom in developing models of computation and a supply of well investigated structures. In particular, there exists an established second-order representation of the set of continuous functions on the unit interval. This representation has been classified as the weakest representation such that evaluation is possible in polynomial time. As a first step we specify the weakest representation of the integrable functions such that integration is polynomial-time computable. This representation turns out to be discontinuous and therefore not suitable. We go on to explore the general restrictions of bounded-time computations on metric spaces within the framework of second-order representations. The notion of metric entropy, originally introduced by Kolmogorov, is used to classify those compact metric spaces that allow for a short representation such that the metric is computable efficiently. To be able to apply the results to spaces of integrable functions we investigate quantitative versions of classification results of their compact subsets called the Arzelà-Ascoli Theorem and the Fréchet-Kolmogorov Theorem. We use the above to propose a family of representations for Lp-spaces. These are shown to be computably equivalent to the standard representations of the same spaces as metric spaces. Furthermore, we prove that the norm can be computed in exponential time. This is also the case for the supremum norm on the continuous functions on the unit interval. A similar family of representations is presented for Sobolev spaces. These representations are investigated in some detail. Several operators on Sobolev spaces are proven to be polynomial-time computable with respect to these representations. For technical reasons only the one-dimensional case is discussed. Finally, we present a result that classifies the computational complexity of the solution operator of the Dirichlet Problem for Poisson’s Equation on the unit disk as that of integrating a continuous function. As a tool for the comparison, polynomial-time Weihrauch reductions are used.

Ort: Darmstadt
Fachbereich(e)/-gebiet(e): 04 Fachbereich Mathematik > Logik
Hinterlegungsdatum: 07 Mai 2017 19:55
Offizielle URL: http://tuprints.ulb.tu-darmstadt.de/6096
URN: urn:nbn:de:tuda-tuprints-60964
Gutachter / Prüfer: Ziegler, Prof. Dr. Martin ; Kohlenbach, Prof. Dr. Ulrich ; Kawamura, Prof. Dr. Akitoshi
Datum der Begutachtung bzw. der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 2 November 2016
Alternatives oder übersetztes Abstract:
AbstractSprache
Motivation für diese Doktorarbeit ist das Vorantreiben der Suche nach einem auf ei- nem realistisches Maschinenmodell basierenden, mathematisch rigorosen Rahmen für Effizienzüberlegungen über die Numerik partieller Differenzialgleichungen. Während die Berechenbarkeitstheorie für kontinuierliche Strukturen auf die meisten Situationen an- wendbar ist und beständig weiter entwickelt wird, ist es selbst in simplen Fällen oft noch unklar, welche Algorithmen als effizient zu gelten haben. In dieser Arbeit wird das Problem im Rahmen der Darstellungen zweiter Ordnung angegangen. Diese beziehen sowohl ihren Namen, als auch ihren Begriff von Polyno- mialzeitberechenbarkeit aus der Komplexitätstheorie der Funktionale auf dem Baire Raum, auch Komplexitätstheorie zweiter Ordnung genannt. Als Maschinenmodell die- nen Orakel-Turingmaschinen. Die Darstellungen zweiter Ordnung bieten viel Freiraum in der Gestaltung von Rechenmodellen und auch einen Grundstock an Konstruktuionen und behandelten Problemen. Insbesondere existiert eine etablierte Darstellung für das Rechnen mit stetigen Funktionen auf dem Einheitsintervall. Diese ist als die schwächste charakterisiert, die eine Auswertung in Polynomialzeit möglich macht. Als ein erster Schritt wird die schwächste Darstellung zweiter Ordnung für die in- tegrierbaren Funktionen angegeben, die es ermöglicht in Polynomialzeit Integrale aus- zuwerten. Unglücklicherweise erweist sich diese als unstetig und damit ungeeignet. Auf der Suche nach einer geeigneteren Darstellung werden die generellen Beschränkungen des Rechnens mit Darstellungen zweiter Ordnung auf metrischen Räumen untersucht. Dabei spielt die von Kolmogorov eingeführte metrische Entropie eines kompakten metrischen Raumes eine tragende Rolle. Es stellt sich heraus, dass es einen direkten Zusammenhang zwischen dieser und der Existenz ‘kurzer’ Darstellungen gibt, bezüglich derer sich die Me- trik ‘schnell’ berechnen lässt. Um diese Resultate auf Räume integrierbarer Funktionen anwendbar zu machen, werden quantitative Versionen der Klassifikationsresultate kom- pakter Teilmengen, bekannt als die Sätze von Arzelà-Ascoli und Fr´ echet-Kolmogorov, untersucht. Auf die gewonnen Erkenntnisse gestützt wird eine Familie von Darstellungen für L p - Räume konstruiert. Es wird beweisen, dass diese berechenbar äquivalent zu den Darstel- lungen selbiger Räume als metrische Räume sind und gezeigt, dass sie die L p -Norm in Exponentialzeit berechnenbar machen. Dies ist auch die Komplexität der Supremums Norm auf den stetigen Funktionen. Eine ähnliche Konstruktion führt zu Darstellungen von Sobolev-Räumen. Die Berechenbarkeit unterschiedlichster Operationen in Polyno- mialzeit wird gezeigt, aus technischen Gründen nur für den eindimensionalen Fall. Abschließend wird ein Resultat präsentiert, das die Schwierigkeit des Berechnens des Lösungsoperators zum Dirichlet-Problem für Poisson’s Gleichung auf der Einheitskugel gleichsetzt mit der Schwierigkeit eine stetigen Funktion zu integrieren. Zum Verglei- chen von Schwierigkeiten von Aufgaben werden Polynomialzeit-Weihrauch-Reduktionen verwendet.Deutsch
Export:

Optionen (nur für Redakteure)

Eintrag anzeigen Eintrag anzeigen