Loading…
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.
Die Berechnung der Homologiegruppen von semialgebraischen 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 Anhang die erwartete Anzahl reeller Nullstellen eines zufälligen Systems polynomialer Gleichungen mit wenigen Termen und geben einen informellen Überblick über das Hauptthema auf Spanisch.
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.
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.
