Applications of Exact Real Computations for Rigorous Solutions
- Efficient and exact solutions to problems involving real numbers and
functions over the reals have notoriously been challenging to compute due to
the uncountable nature of the reals and the accumulation of numerical errors.
This thesis describes methods and software implementations for
computing solutions to such problems along with benchmarks and rigorous
correctness proofs. Specifically presented are a calculus for solving non-linear,
transcendental SMT problems over real numbers, methods for solving initial value
problems, and a framework for rigorously analysing and optimising machine learning
models.
These techniques and tools are based on exact real computations and thus provide
exactness guarantees for real-valued results based on formal methods.
The techniques employed range from Taylor models to local linearisations and
are proven to be correct. In particular, a CDCL-style calculus for solving
non-linear constraints which underlies the published SMT solver ksmt is
provided along with proofs of soundness and δ-completeness. The
techniques and tools presented here compare favourably to state-of-the-art
solvers and are available as open-source software.
- Probleme mit reellen und Zahlen und Funktionen sind aufgrund ihrer
überabzählbaren Natur und der Anhäufung numerischer Fehler bekannt dafür, dass
die effiziente und exakte Berechnung von Lösungen schwierig ist. Die
vorliegende Arbeit beschreibt Methoden und Softwareimplementierungen zur
Berechnung von Lösungen solcher Probleme, liefert Korrektheitsbeweise und
untersucht mittels Benchmarks deren Praktikabilität.
Insbesondere werden ein Kalkül zur Lösung
nichtlinearer, transzendenter SMT-Probleme über den reellen Zahlen, Methoden zur
Lösung von Anfangswertproblemen und ein Framework für die gründliche Analyse und
Optimierung von Machine-Learning-Modellen vorgestellt.
Diese Techniken und Werkzeuge basieren auf exakten Berechnungen mit reellen
Zahlen, und liefern somit -- basierend auf formalen
Methoden -- Garantien für die Exaktheit ihrer reell-wertigen Ergebnisse. Die
eingesetzten Techniken reichen von Taylor-Modellen bis hin zu lokalen
Linearisierungen, deren Korrektheit bewiesen wird. Besonders hervorzuheben ist
der CDCL-artige Kalkül zur Lösung nichtlinearer Probleme, der dem
veröffentlichten SMT-Solver ksmt zugrunde liegt, und der zusammen mit Beweisen
für seine Korrektheit und δ-Vollständigkeit präsentiert wird. Die hier
vorgestellten Techniken und Werkzeuge schneiden im Vergleich mit anderen
modernen Solvern gut ab. Sie sind als Open-Source-Software frei verfügbar.
Metadaten| Author: | Franz Brauße |
|---|
| URN: | urn:nbn:de:hbz:385-1-29644 |
|---|
| Advisor: | Norbert Müller |
|---|
| Document Type: | Doctoral Thesis |
|---|
| Language: | English |
|---|
| Date of completion: | 2026/10/05 |
|---|
| Publishing institution: | Universität Trier |
|---|
| Granting institution: | Universität Trier, Fachbereich 4 |
|---|
| Date of final exam: | 2025/09/29 |
|---|
| Release Date: | 2026/10/06 |
|---|
| Number of pages: | XVI, 134 |
|---|
| First page: | I |
|---|
| Last page: | 134 |
|---|
| Institutes: | Fachbereich 4 |
|---|
| Licence (German): | InCopyright: Urheberrechtsschutz |
|---|