A dimension-oblivious domain decomposition method based on space-filling curves

1. Probleemstelling

Het artikel adresseert de uitdaging om hoog-dimensionale elliptische partiële differentiaalvergelijkingen (PDE's), specifiek de Poisson-vergelijking, op te lossen op moderne exascale-computersystemen. De kernproblemen die worden geïdentificeerd zijn:

• Vervloeking van de Dimensionaliteit: Standaard discretisatiemethoden (volledige roosters) worden onuitvoerbaar naarmate de dimensie $d$ toeneemt, vanwege de exponentiële groei in vrijheidsgraden (DOF's).
• Anisotrope Roosters: De "Sparse Grid Combination Technique" wordt gebruikt om de vervloeking van de dimensionaliteit te mitigeren. Deze methode decomposeert het probleem in vele onafhankelijke subproblemen op anisotrope roosters (waarbij roostergroottes $h_j$ per dimensie variëren). Traditionele geometrische domeindecompositie (DD)-methodes kampen hiermee omdat ze afhankelijk zijn van geometrische informatie met een vaste dimensionaliteit, wat moeilijk te definiëren is voor willekeurige anisotrope roosters.
• Fouttolerantie en Schaalbaarheid: Toekomstige exascale-systemen vereisen algoritmes die niet alleen schaalbaar zijn tot miljoenen kernen, maar ook fouttolerant. Het bereiken van fouttolerantie in numerieke oplosmethodes vereist doorgaans data-redundantie, wat impliceert dat er grote overlappingen moeten zijn tussen subdomeinen in een DD-methode. Conventionele DD-methodes minimaliseren overlapping om communicatiekosten te verlagen, wat een conflict creëert met de noodzaak aan redundantie.
• Dimensie-onbewustheid: De oplosser moet algebraïsch opereren op de samengestelde matrixvergelijkingen zonder afhankelijk te zijn van geometrische coördinaten, waardoor het willekeurige dimensies en anisotrope roosters uniform kan verwerken.

2. Methodologie

De auteurs stellen een twee-niveau algebraïsche domeindecompositie-oplosser voor die gebaseerd is op Ruimtevullende Curven (SFC's).

A. Partitionering via Ruimtevullende Curven

In plaats van geometrische partitionering, kabbelt de methode de $d$-dimensionale roosterpunten af op een één-dimensionale parameterruimte $[0, 1]$ met behulp van een discrete ruimtevullende curve (specifiek de Hilbert-curve).

• Mapping: Roosterpunten worden gesorteerd volgens de SFC.
• Disjuncte Partitionering: De gesorteerde reeks van $N$ punten wordt opgesplitst in $P$ aaneengesloten deelverzamelingen van ongeveer gelijke grootte ($N/P$). Dit zorgt voor een gebalanceerde last, ongeacht de dimensie $d$ of de anisotropie van het rooster.
• Overlappingsconstructie: Om data-redundantie voor fouttolerantie te bereiken, worden de disjuncte deelverzamelingen vergroot. In plaats van geometrische grenslagen toe te voegen, voegt de methode aangrenzende indexverzamelingen toe vanuit de 1D SFC-sorteervolgorde. Een overlapparameter $\gamma$ bepaalt hoeveel aangrenzende subdomeinen worden opgenomen.
  • Voor $\gamma = 0.5$ wordt elk roosterpunt gedekt door precies $2\gamma + 1 = 2$ subdomeinen.
  • Voor gehele veelvouden van $0.5$ is de overlap uniform, wat symmetrie in de resulterende operatoren garandeert.

B. Algebraïsche Twee-Niveau Oplosser

De oplosser wordt puur algebraïsch geconstrueerd, waarbij geometrische grove roosters worden vermeden:

1. Fijn Niveau (Lokale Subdomeinen): Elke processor lost een lokaal probleem op zijn overlappende subdomein $\Omega_i$ op.
2. Grove Niveau (Globale Correctie): Een grove ruimte wordt algebraïsch gedefinieerd. In plaats van een geometrisch grof rooster, wordt de grove ruimte geconstrueerd door $q$ vrijheidsgraden per subdomein toe te wijzen op basis van de SFC-sorteervolgorde. De grove matrix $A_0$ wordt gevormd via de Galerkin-aanpak ($A_0 = R_0 A R_0^T$).
3. Redundantie (Bank-Holst Techniek): Het grove probleem wordt redundante op elke processor opgelost, naast het lokale subprobleem. Dit vermijdt communicatiebottlenecks die geassocieerd zijn met één enkel globaal grof oplossen en ondersteunt fouttolerantie.
4. Gewichting: Om de overtelling van onbekenden in overlappende regio's te verwerken, wordt een eenheidsverdeling toegepast. De auteurs tonen aan dat voor specifieke keuzes van $\gamma$ (veelvouden van $0.5$), de wegingsmatrices $D_i$ scalaire veelvouden van de eenheidsmatrix worden, waardoor de symmetrie van de operator behouden blijft. Dit maakt het gebruik van de Conjugate Gradient (CG)-methode mogelijk.

C. Iteratieve Schema's

De methode wordt geïmplementeerd als:

• Een gedempte Richardson-iteratie (Additieve Schwarz).
• Een voorconditioneerde Conjugate Gradient (PCG)-methode.
• Beide maken gebruik van de twee-niveau operator (Lokale oplossingen + Grove correctie).

3. Belangrijkste Bijdragen

• Dimensie-onbewuste Oplosser: De eerste DD-oplosser die direct werkt op samengestelde matrices met behulp van SFC's, waardoor het toepasbaar is op elke dimensie $d$ en elke anisotrope roosterstructuur zonder geometrische aannames.
• Grote Overlap voor Fouttolerantie: Het artikel ontwerpt de DD-methode bewust met grote overlappingen (gecontroleerd door $\gamma$) om de data-redundantie te bieden die noodzakelijk is voor fouttolerant rekenen op exascale-systemen, een afwijking van traditionele DD die overlapping minimaliseert.
• Algebraïsch Grof Rooster: Een puur algebraïsche constructie van de grove ruimte die de complexiteit vermijdt van het definiëren van geometrische grove roosters voor anisotrope of hoog-dimensionale problemen.
• Behoud van Symmetrie: Theoretisch bewijs (Lemma 3.1) dat het kiezen van $\gamma$ als een veelvoud van $0.5$ resulteert in symmetrische operatoren, waardoor het gebruik van efficiënte symmetrische oplosmethodes zoals PCG mogelijk is, zelfs met grote overlappingen.

4. Numerieke Resultaten

De auteurs hebben uitgebreide numerieke experimenten uitgevoerd op dimensies $d=1$ tot $6$ met gebruik van tot wel één miljoen processors.

• Convergentiegedrag:

  • De oplosser vertoont optimale zwakke schaalbaarheid: Het aantal iteraties dat nodig is om te convergeren blijft constant naarmate het aantal processors $P$ toeneemt (bij een vastgehouden probleemgrootte per processor).
  • Dimensie-onafhankelijkheid: De convergentiesnelheid is grotendeels onafhankelijk van de dimensie $d$. Interessant genoeg is het 1D-geval het moeilijkste (langzaamste convergentie) vanwege de relatieve afstand tussen fijne en grove schalen; hogere dimensies convergeren eigenlijk sneller of vergelijkbaar.
  • PCG vs. Richardson: De voorconditioneerde Conjugate Gradient-methode presteert aanzienlijk beter dan de Richardson-iteratie, waarbij ongeveer de helft van het aantal iteraties nodig is.
  • Overlapparameter: Een overlap van $\gamma = 0.5$ biedt de beste balans tussen convergentiesnelheid en redundantie. Een grotere $\gamma$ verbetert de fouttolerantie maar verhoogt het aantal iteraties licht (tenzij correct gewogen).

• Schaalbaarheid in Combination Technique:

  • De methode is geïntegreerd in de Sparse Grid Combination Technique.
  • Massieve Parallelisme: De aanpak heeft succesvol gebruik gemaakt van meer dan 1 miljoen processors voor een 6-dimensionaal probleem.
  • Lastbalans: De SFC-partitionering zorgde ervoor dat elke processor ongeveer hetzelfde aantal DOF's ($2^8$) verwerkte, wat resulteerde in zeer uniforme looptijden over alle subproblemen.
  • Efficiëntie: De looptijd per subprobleem bleef constant naarmate de totale systeemgrootte groeide, wat ware zwakke schaalbaarheid demonstreert.

5. Betekenis

Dit werk biedt een kritiek bouwsteen voor exascale computing in hoog-dimensionale PDE's.

• Schaalbaarheid: Het lost de "vervloeking van de dimensionaliteit" niet alleen op door het gebruik van sparse roosters, maar door de Sparse Grid Combination Technique efficiënt te laten draaien op miljoenen kernen.
• Fouttolerantie: Door de focus te verschuiven van het minimaliseren van communicatie (kleine overlap) naar het maximaliseren van redundantie (grote overlap), ebt de methode de weg voor oplosmethodes die hardware-fouten kunnen overleven zonder de hele simulatie te moeten herstarten.
• Generaliteit: De algebraïsche, dimensie-onbewuste aard van de oplosser betekent dat deze kan worden toegepast op een breed scala aan problemen (elliptisch, parabolisch) en discretisaties (finite difference, finite element) zonder dimensie-specifieke geometrische afstemming nodig te hebben.

Kortom, het artikel presenteert een robuuste, schaalbare en fouttolerante lineaire oplosser die ruimtevullende curven benut om het domeindecompositieproces te ontkoppelen van de geometrische dimensie van het probleem, waardoor de efficiënte oplossing van hoog-dimensionale PDE's op toekomstige supercomputers mogelijk wordt.