Doctoral thesis


The thesis is in the process of publication.


Condition and Homology in Semialgebraic Geometry



Cover page of Conditionand Homology in Semialgebraic Geometry by Josué Tonelli-Cueto
Josué Tonelli-Cueto holding a copy of his doctoral thesis

Abstract

The computation of the homology groups of semialgebraic sets (given by Boolean formulas) remains one of the open challenges of computational semialgebraic geometry. Despite the search for an algorithm taking singly exponential time only on the number of variables, as of today, the existing algorithms are symbolic and doubly exponential. In this PhD thesis, we show how to obtain a numerical algorithm running in single exponential time with very high probability, which improves the state-of-the-art. To do so, we explain the underlying ideas, methods and techniques from numerical algebraic geometry, numerical complexity and topological data analysis that made this progress possible. We finish with a list of open problems and questions pointing to a possible future of the numerical computation of topological invariants.

Additionally, in the appendices, we cover the topic of the expected number of real zeros of a random fewnomial system and we give an accessible account of the central theme in Spanish.

Zusammenfassung (Abstract in German)

Die Berechnung der Homologiegruppen von semialgebraichen Mengen (gegeben durch boolesche Formeln) bleibt eine der offenen Herausforderungen der algorithmischen semialgebraischen Geometrie. Trotz der Suche nach einem Algorithmus mit einfach exponentieller Laufzeit in der Anzahl der Variablen, sind die nach heutigem Stand bekannten Algorithmen symbolisch und doppelt exponentiell. In dieser Doktorarbeit zeigen wir, wie man einen numerischen Algorithmus konstruiert, der mit großer Wahrscheinlichkeit einfach exponentiell ist und somit den Stand der Forschung verbessert. Dazu erklären wir die zugrundliegenden Ideen, Methoden und Techniken von numerischer algebraischen Geometrie, numerischer Komplexität und topologischer Datenanalyse, die dieser Fortschrift möglich machten. Wir enden mit einer Liste offener Probleme und Fragen, die auf eine mögliche Zukunft von Berechnung der topologischen Invarianten weisen.

Außerdem, behandeln wir im Anhange die erwartete Anzahl reeller Nullstellen eines zufälligen Systems polynomialer Gleichungen mit wenigen Termen und geben einen informellen Überblick über das Hauptthema auf Spanisch.

Laburpena (Abstract in Basque)

Multzo semialjebraikoen (formula boolearrek emandakoen) homologia-taldeak kalkulatzeak jarraitzen du, oraindik ere, geometria semialjebraiko konputazionalaren erronka handienetako bat izaten. Bilatzen den algoritmoak aldagai kopuruan baino ez du hartzen denbora behin esponentziala; hala ere, gaur egun dauden algoritmo guztiak sinbolikoak eta bi aldiz esponentzialak dira. Doktorego-tesi honetan erakusten dugu nola lor daitekeen debora behin esponentzialean eta probabilitate handiarekin exekutatzen den zenbakizko algoritmo bat; hori teknikaren egoeraren hobekuntza da. Horretarako, zenbakizko geometria aljebraikoaren, zenbakizko konplexutasunaren eta datu-analisi topologikoaren azpian dauden eta aurrerapen hori posible egin duten ideia, metodo eta teknikak azaltzen ditugu. Problemen eta galdera irekien zerrenda batekin bukatzen dugu, zeinek inbariante topologikoen zenbakizko konputazioaren etorkizun posible bat adierazten baitute.

Gainera, eranskinetan, ausazko sistema oligonomiko baten zero kopurua aztertzen dugu, eta tesi honen ikuspegi informala ematen dugu gaztelaniaz.

Resumen (Abstract in Spanish)

El cálculo de los grupos de homología de conjuntos semialgebraicos (dados por fórmulas booleanas) es todavía uno de los mayores desafíos de la geometría semialgebraica computacional. Aunque se busca un algoritmo que tome a lo sumo tiempo simplemente exponencial en el número de variables, hasta el día de hoy todos los algoritmos existentes son simbólicos y doblemente exponenciales. En esta tesis doctoral, mostramos cómo se puede obtener un algoritmo numérico que tome tiempo simplemente exponencial con alta probabilidad, lo cual es una mejora del estado del arte. Para ello, explicamos las ideas, métodos y técnicas subyacentes procedentes de la geometría algebraica numérica, de la complejidad numérica y del análisis topológico de datos que han hecho posible este progreso. Terminamos con una lista de problemas y preguntas abiertas que indican un posible futuro de la computación numérica de invariantes topológicos.

Además, en los apéndices, estudiamos el número esperado de ceros reales de un sistema oligonómico aleatorio y damos una visión informal del tema principal de esta tesis en castellano.


Doctoral evaluation

The doctoral thesis was handed in on the 11th of October of 2019. The evaluators of the thesis were Peter Bürgisser, Felipe Cucker and Pierre Lairez. After the evaluators approved the thesis, the doctoral defence took place on the 28th of November of 2019 at 12:00 at the room MA313/314 in the 3rd floor of the Institut für Mathematik of the Technische Universität Berlin (Str. des 17. Juni 136). The defence committee was presided by John M. Sullivan and it was formed by the evaluators Peter Bürgisser, Felipe Cucker and Pierre Lairez. After a successful defence, there was a small celebration with food and drinks in the Matheon Lounge (MA315). Currently, the final version of the thesis for publication is under preparation. After the publication of this final version, the degree of doctor will be officially issued.

The official name of the obtained academic degree will be Doktor der Naturwissenschaften (Dr. rer. nat.), which means “doctor in natural sciences”. In the anglosaxon academic system, this degree is equivalent to a PhD. The final grade of the doctorate (when issued) will be “mit Auszeichnung bestanden” (summa cum laude), which is the maximum grade obtained only when all the evaluators give the maximum grade to both the thesis and the defence.