Toegepaste en computationele algebraïsche meetkunde

Voorgestelde schets van het proefschrift:Dit voorstel is gebaseerd op toegepaste en computationele algebraïsche meetkunde. Algebraïsche meetkunde is de studie van variëteiten die worden gedefinieerd als de nulreeksen van stelsels van polynoomvergelijkingen. We zullen ons concentreren op de polynomiale systemen die voortkomen uit specifieke problemen in de theoretische informatica. In het bijzonder zullen we theorie en algoritmen voor onze toepassingen ontwikkelen op basis van de volgende takken van algebraïsche meetkunde:[T1] Numerieke algebraïsche meetkunde: Numerieke algebraïsche meetkunde [SW05] is, zoals de naam al doet vermoeden, de samensmelting van numerieke technieken en algebraïsche meetkunde. Het hoofddoel van deze theorie is het ontwikkelen van nieuwe hulpmiddelen voor het numeriek oplossen van het stelsel van polynoomvergelijkingen. De twee belangrijkste technieken die in het gebied worden gebruikt, zijn homotopie-voortzettings- en eigenwaardemethoden. De eerste gebruikt geschikte homotopieën om het gegeven stelsel van polynoomvergelijkingen te vervormen tot een stelsel dat gemakkelijk kan worden opgelost. Volg vervolgens alle oplossingen van het vervormde systeem naar het oorspronkelijke systeem, samen met de gekozen homotopie. Deze methode helpt bij het vinden van alle oplossingen van het systeem in tegenstelling tot de andere numerieke oplossers. De eigenwaardemethode zet het probleem van het oplossen van het stelsel van polynoomvergelijkingen om in het oplossen van het eigenwaardeprobleem voor overeenkomstige Macaulay-matrices [Te20]. Om de Macaulay-matrices te berekenen, is deze methode gebaseerd op symbolische berekeningen. Om het eigenwaardeprobleem op te lossen, vertrouwt deze methode op algoritmen uit computationele lineaire algebra. Beide methoden bieden numerieke oplossingen voor het stelsel van polynoomvergelijkingen. Om deze oplossingen in toepassingen te gebruiken, hebben we wiskundige certificaten nodig, hiervoor gebruiken we de theorie van Smale [HS10] en de methode van Krawczyk. In recente werken [Br20], [Te20] zijn nieuwe technieken uit de polyedrische meetkunde en de torische meetkunde gebruikt om numerieke algoritmen te ontwikkelen voor het oplossen van schaarse polynoomsystemen.[T2] Reële algebraïsche meetkunde: Reële algebraïsche meetkunde [BCR13] is de tak van de algebraïsche meetkunde die zich bezighoudt met het vinden van reële oplossingen voor de veeltermvergelijkingen. De belangrijkste concepten van dit gebied zijn onder meer de eliminatie van kwantoren, decompositiestellingen voor semi-algebraïsche verzamelingen, de bestaanstheorie van reële getallen, Positivstellensatz enz. In de toepassingen zijn we vooral geïnteresseerd in het vinden van de reële oplossingen voor het stelsel van polynoomvergelijkingen. De klassieke stellingen uit dit gebied (bijvoorbeeld de Positivstellensatz van Putinar) zijn al in gebruik. Maar de volledige kracht van deze theorie is niet volledig benut in de toepassingen waarin we geïnteresseerd zijn. Met name de existentietheorie van reële getallen en decompositiestellingen kan zeer nuttig zijn voor het ontwikkelen van voldoende voorwaarden voor het bestaan van reële oplossingen voor de polynoomsystemen onder overweging. Er zijn ook recente vorderingen gemaakt bij het vinden van echte numerieke oplossingen voor de veeltermvergelijkingen met behulp van technieken uit de tropische meetkunde en veelvlakkige meetkunde. Bovendien zijn voor bepaalde schaarse polynomiale systemen zeer recent ook enkele nieuwe algoritmen voor het tellen van reële oplossingen voorgesteld, die nuttig kunnen zijn voor de complexiteitsanalyse van onze problemen.[T3] Symbolische berekeningen: Symbolische berekeningen gaan over het oplossen van stelsels van polynoomvergelijkingen met behulp van technieken uit de theorie van Gröbner-basis en eliminatietheorie [CLO13]. Deze methoden verschillen aanzienlijk van numerieke algebraïsche meetkunde, omdat de theorie hier afhangt van algebraïsche manipulaties van vergelijkingen in plaats van te vertrouwen op numerieke bewerkingen. Maar beide methoden vullen elkaar aan, want voor bepaalde numerieke technieken zoals eigenwaardemethoden [T1], is een van de cruciale stappen de berekening van de Gröbner-basis. Hoewel de complexiteit van de berekening van de Gröbner-basis voor een algemeen polynoomsysteem dubbel exponentieel is in de omvang van het probleem, is deze methode nog steeds nuttig voor onze toepassing. Omdat de systemen waarin we geïnteresseerd zijn mooie combinatorische structuren hebben (sparsity, lage boombreedte, enz.), zijn de Gröbner-basisberekeningen voor dergelijke systemen handelbaar. In het bijzonder is het belangrijkste idee om te bewijzen dat onze systemen een bepaalde vorm van Gröbner-basis hebben, wat op zijn beurt kan helpen om de tijdcomplexiteit voor het berekenen van de Macaulay-matrices die nodig zijn voor de eigenwaardemethoden te verminderen. Voor schaarse polynomiale systemen zijn er recente ontwikkelingen geweest voor de efficiënte berekeningen van de Gröbner-basis met behulp van eigenschappen van de grafieken die zijn geassocieerd met de polynoomsystemen in overwegingen [Pa14]. Er zijn ook nieuwe resultaten in de complexiteitsanalyse voor de berekening van de Gröbner-basis voor sparse systemen [Be19]. Deze nieuwe resultaten kunnen van enorm nut zijn voor onze voorgestelde problemen.We zullen de bovengenoemde takken van de algebraïsche meetkunde gebruiken om de echte wortels te vinden van het stelsel van polynoomvergelijkingen die in de theoretische informatica ontstaan. Met name op het gebied van programmaverificatie zijn er recente ontwikkelingen en nieuwe verbindingen uit de algebraïsche meetkunde [Go20]. We zullen ons concentreren op

Trefwoorden:Algebraic Geometry, Theoretical Computer Science, Program Verification

Disciplines:Computerwetenschappen, Computationele logica en formele talen, Algebraïsche geometrie

Project type:PhD project