< Terug naar vorige pagina

Project

Het oplossen van veeltermsystemen

Stelsels veeltermvergelijkingen duiken op in talrijke problemen in toegepaste wiskunde en ingenieurswetenschappen. Voorbeelden van zulke problemen kan men vinden in onder meer de robotica, chemische ingenieurstechnieken, computervisie, dynamische systeemtheorie, signaalverwerking en geometrische modellering. Het numeriek oplossen van een stelsel veeltermvergelijkingen wordt beschouwd als een uitdagend probleem in de computationele wiskunde. Belangrijke klassen van bestaande methodes zijn algebraïsche methodes, die het probleem oplossen via eigenwaardenberekeningen, en homotopiemethodes, die oplossingspaden volgen in een continue vervorming van het stelsel. In deze tekst stellen we nieuwe algoritmes voor van beide soorten die op verschillende vlakken beter presteren dan de bestaande methodes.

Klassieke voorbeelden van algebraïsche technieken maken gebruik van Gröbner-basissen, border-basissen of resultanten. Deze methodes zijn gebaseerd op het feit dat de oplossingen geëncodeerd zijn in de structuur van een algebra die op een natuurlijke manier door de vergelijkingen van het stelsel wordt gedefiniëerd. Om berekeningen te doen in deze algebra kiezen de algoritmes een voorstelling ervan die gebruikelijk bestaat uit een aantal monomen die aan zekere voorwaarden voldoen. In deze thesis tonen we aan dat deze voorwaarden vaak te strikt zijn en mogelijk leiden tot ernstige numerieke onstabiliteit van de algoritmes. Dit resulteert in het feit dat ze niet geschikt zijn voor berekeningen in eindige precisie. We stellen het raamwerk van afgeknotte normaalvormen (truncated normal forms, TNFs) voor om deze tekortkoming te verhelpen en ontwikkelen nieuwe, robuuste en gestabiliseerde methodes. Het raamwerk veralgemeent Gröbner- en border-basissen, alsook een aantal resultant-gebaseerde algoritmes. We stellen expliciete constructies voor om vierkante systemen op te lossen die `generiek' gedrag vertonen, waarmee we bedoelen dat ze het verwachte aantal oplossingen hebben in de zin van Bézout of Bernstein-Khovanskii-Kushnirenko. We tonen aan hoe de voorgestelde technieken gebruikt kunnen worden in een homogene context door het definiëren van homogene normaalvormen (homogeneous normal forms, HNFs) die een elegante manier bieden om oplossingen `op oneindig' af te handelen. Bijvoorbeeld, homogene normaalvormen kunnen gebruikt worden om stelsels op te lossen die eindig veel oplossingen definiëren in de projectieve ruimte door te werken in de homogene coördinaatring. We ontwikkelen de nodige theorie om deze aanpak te veralgemenen naar de homogene coördinaatring (of Cox ring) van een compacte torische variëteit. Op deze manier bekomen we een algoritme voor het oplossen van veeltermstelsels in een compactificatie van de algebraïsche torus die rekening houdt met de polyhedrale structuur van de vergelijkingen. Deze aanpak is vooral effectief in het geval waarin het systeem oplossingen definiëert nabij de rand van de torus in zijn compactificatie, hetgeen typisch een probleem vormt voor andere methodes. Elk van de voorgestelde algoritmes wordt getest in numerieke experimenten en vergeleken met bestaande implementaties.

Homotopiemethodes zijn wellicht de meest populaire methodes voor het numeriek oplossen van een stelsel veeltermvergelijkingen. Éen van de redenen daarvoor is dat de rekenkost veel beter schaalt met het aantal variableen in het stelsel dan voor algebraïsche methodes. Echter, de betrouwbaarheid van deze methodes hangt sterk af van een aantal ontwerpkeuzes in het algoritme. Een belangrijk voorbeeld is de keuze van de stapgrootte in de discretisatie van de oplossingspaden. Kiezen we deze te klein dan leidt dit tot lange rekentijden. Kiezen we deze te groot dan kan dit leiden tot path jumping, wat een typische oorzaak is voor verloren oplossingen in de output van een homotopie algoritme. In deze thesis ontwerpen we een nieuw homotopie algoritme dat gebruik maakt van een adaptieve stapgrootte en tonen we aan dat dit algoritme beduidend minder last heeft van path jumping dan state-of-the-art alternatieven.

Datum:22 sep 2016  →  21 sep 2020
Trefwoorden:polynomials, resultants, numerical linear algebra
Disciplines:Toegepaste wiskunde, Computerarchitectuur en -netwerken, Distributed computing, Informatiewetenschappen, Informatiesystemen, Programmeertalen, Scientific computing, Theoretische informatica, Visual computing, Andere informatie- en computerwetenschappen
Project type:PhD project