Space-time waveform relaxation multigrid for Navier-Stokes

Dit artikel presenteert een schaalbare monolithische Newton-Krylov-multigrid-oplosser voor de Navier-Stokes-vergelijkingen, die waveform relaxation-multigrid-methode combineert met ruimtetijd-vinite-elementdiscretisatie voor een efficiënte all-at-once-benadering.

De kern

Hier is een uitleg van het onderzoek van Jackaman en MacLachlan, vertaald naar begrijpelijk Nederlands met behulp van alledaagse analogieën.

De Grote Uitdaging: Het Voorspellen van Stroomlijnen

Stel je voor dat je een superkrachtige computer hebt die kan voorspellen hoe water stroomt, hoe wind door een stad waait, of hoe bloed door aderen stroomt. Dit is wat wetenschappers doen met de Navier-Stokes-vergelijkingen. Het is een wiskundig monster dat alles beschrijft over vloeistoffen.

Het probleem is dat deze berekeningen enorm zwaar zijn. Je moet de ruimte (waar het water is) én de tijd (hoe het water beweegt) tegelijkertijd berekenen.

Het Oude Moeilijkheidsprobleem: De "Eén voor Eén" Benadering

Vroeger (en vaak nog steeds) deden computers dit als een rekenmachine in een rij.

• Ze berekenden de situatie op tijdstip 1.
• Daarna tijdstip 2.
• Dan tijdstip 3.
• En zo verder tot het einde.

Stel je voor dat je een lange rij mensen hebt die een emmer water van A naar B moeten dragen. De eerste persoon doet het, geeft het door aan de tweede, die het weer doorgeeft. Zelfs als je 1000 mensen (computerkernen) hebt die ruimtelijk kunnen helpen, moeten ze toch wachten tot de vorige persoon klaar is. Als de rij te lang wordt, staan de mensen in de weg en wordt het proces traag. Dit noemen ze tijd-sequentiële berekening.

De Nieuwe Oplossing: De "Alles Tegelijk" Methode

De auteurs van dit papier hebben een slimme nieuwe manier bedacht om dit op te lossen. Ze noemen het Space-Time Waveform Relaxation Multigrid. Dat klinkt ingewikkeld, maar het is eigenlijk als het organiseren van een gigantisch orkest.

In plaats van dat iedereen één voor één speelt, laten ze iedereen tegelijk spelen.

• Ze nemen de hele tijdlijn (van begin tot einde) en verdelen die over honderden computers.
• Computer A doet de eerste 10 seconden, Computer B doet de 10 tot 20 seconden, enzovoort.
• Ze werken allemaal tegelijk aan hun stukje van de tijd.

Maar hier is de truc: als Computer A iets verkeerd doet, kan dat invloed hebben op Computer B. Ze moeten dus constant "overleggen" om hun berekeningen op elkaar af te stemmen. Dit overleg noemen ze Waveform Relaxation. Het is alsof het orkest een paar keer repeteert: "Oké, jij speelde net iets te hard, pas dat aan, en dan proberen we het opnieuw."

De "Multigrid" Superkracht: Van Groot naar Klein

Nu komt het tweede slimme onderdeel: Multigrid.
Stel je voor dat je een enorme, rommelige tekening moet corrigeren.

1. Je kijkt eerst naar de hele tekening van veraf (een grof raster). Je ziet direct de grote fouten (bijvoorbeeld: "die berg is te hoog"). Dat is makkelijk en snel op te lossen.
2. Dan zoom je in (een finer raster) om de kleine details te fixen.
3. Je gaat heen en weer tussen "veraf kijken" (groot) en "dichtbij kijken" (klein).

In dit onderzoek gebruiken ze deze techniek niet alleen voor de ruimte, maar ook voor de tijd. Ze kijken naar de hele tijdslijn van veraf om grote fouten te zien, en zoomen dan in op specifieke momenten om details te verbeteren. Dit maakt de berekening extreem snel en efficiënt.

Wat hebben ze bewezen?

De auteurs hebben hun nieuwe methode getest op twee dingen:

1. Warmteverspreiding: Een simpele test (zoals hoe een pan opwarmt).
2. Vloeistofstroming: Een ingewikkelde test (zoals water in een bak dat van boven wordt bewogen, de "lid-driven cavity").

De resultaten:

• Voor kleine problemen was de oude methode (één voor één) nog steeds snel.
• Maar voor grote, complexe problemen (veel details, veel tijd) was hun nieuwe methode veel krachtiger.
• Ze hebben een model gemaakt dat laat zien: als je een supercomputer met duizenden kernen hebt, kan deze nieuwe methode de berekening veel sneller doen dan de oude methode, omdat hij alle kernen tegelijk gebruikt voor de tijd.

Waarom is dit belangrijk?

Vroeger dachten we dat we alleen maar sneller konden worden door meer ruimte (meer kernen) toe te voegen. Maar op een gegeven moment stopt dat effect; de computers praten te veel met elkaar en worden traag.

Deze nieuwe methode opent de deur naar tijd-parallelisme. Het betekent dat we in de toekomst veel complexere simulaties kunnen draaien (bijvoorbeeld voor weervoorspellingen of het ontwerpen van vliegtuigen) die nu onmogelijk zijn, omdat we eindelijk de tijd-as van de berekening ook kunnen versnellen.

Samenvatting in één zin

De auteurs hebben een slimme manier bedacht om vloeistofstromingen te berekenen waarbij ze niet wachten tot elke seconde klaar is, maar alle seconden tegelijk laten berekenen door een heel team computers, waardoor ze in de toekomst veel sneller en nauwkeuriger voorspellingen kunnen doen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Space-Time Waveform Relaxation Multigrid for Navier-Stokes" van James Jackaman en Scott MacLachlan, in het Nederlands.

Titel: Ruimte-Tijd Golfvorm Relaxatie Multigrid voor Navier-Stokes

1. Probleemstelling

Hoogwaardige simulaties van vloeistofstromen (Computational Fluid Dynamics - CFD) zijn een kernonderdeel van wetenschappelijk rekenen. Traditionele methoden gebruiken vaak een "timestepping"-aanpak, waarbij het probleem per tijdstap wordt opgelost. Op moderne manycore HPC-systemen (High Performance Computing) stoten deze methoden echter snel op een limiet:

• Parallellisatiebeperking: Het is moeilijk om meer dan enkele duizenden vrijheidsgraden per processor te benutten via ruimtelijke parallelisatie alleen. De communicatiekosten wegen dan op tegen de snelheidswinst van het toevoegen van meer kernen.
• Complexiteit van bestaande tijdsparallelle methoden: Bestaande tijdsparallelle algoritmen (zoals Parareal of MGRIT) worden vaak alleen getest op eenvoudige diffusieproblemen. Hun prestaties lijden vaak onder complexere modellen, zoals de hyperbolische aard van de Navier-Stokes-vergelijkingen, tenzij er ingrijpende en kostbare aanpassingen worden gedaan.
• Gebrek aan geavanceerde oplosmethoden: Er is een tekort aan efficiënte "all-at-once" (monolithische) oplosmethoden voor ruimte-tijd discretisaties van de Navier-Stokes-vergelijkingen, vooral voor hogere-orde finite-element methoden.

2. Methodologie

De auteurs ontwikkelen een Waveform Relaxation Multigrid (WRMG) methode voor de "all-at-once" oplossing van de discretiseerde Navier-Stokes-vergelijkingen. In plaats van tijd stap-voor-stap te doorlopen, wordt het probleem over het volledige ruimte-tijd domein simultaan opgelost.

• Discretisatie:
  • Ruimte: Gebruik van continue Lagrange finite-elementen (voor warmtevergelijking) en Taylor-Hood elementen (P2-P1 en P3-P2) voor de Navier-Stokes-vergelijkingen (snelheid en druk).
  • Tijd: Gebruik van discontinu Galerkin (DG) elementen in de tijd (upwind), wat leidt tot een ruimte-tijd finite-element discretisatie op prismatische roosters.
• Multigrid Cyclus:
  • De methode gebruikt een geometrische multigrid V-cyclus als preconditioner voor FGMRES (Flexible Generalized Minimal Residual).
  • Relaxatie: In plaats van puntsgewijze relaxatie, gebruiken de auteurs patch-based relaxatie.
    • Voor de warmtevergelijking: Vertex-star patches.
    • Voor Navier-Stokes: Een uitgebreide Vanka+star relaxatie. Hierbij worden patches gedefinieerd rondom elke hoekpunt, inclusief alle snelheids-vrijheidsgraden (DoFs) in de ster van het punt en alle druk-DoFs op die ster. Deze patches worden over het volledige tijdshorizon "uitgerekt" (waveform relaxation).
  • Grid Transfer: Interpolatie en restrictie operatoren worden gedefinieerd als tensorproducten van de ruimtelijke operatoren en de eenheidsoperator in de tijd.
• Implementatie:
  • De code is geïmplementeerd in Firedrake en PETSc.
  • Er wordt gebruik gemaakt van "extruded mesh" functionaliteit om ruimte-tijd roosters en patches efficiënt te beheren.
  • Voor de lineaire systemen binnen de Newton-iteraties wordt FGMRES gebruikt, met Chebyshev-versnelling voor de relaxatie.

3. Belangrijkste Bijdragen

1. Extensie naar Navier-Stokes: De auteurs tonen aan dat efficiënte ruimtelijke relaxatiemethoden (uit eerdere werk [47]) succesvol kunnen worden uitgebreid naar een waveform relaxatie methode voor ruimte-tijd discretisaties van de Navier-Stokes-vergelijkingen.
2. Hogere Orde en Taylor-Hood Elementen: In tegenstelling tot eerdere werken (zoals [45] die beperkt was tot lage-orde eindige volumes en BDF(2)), ondersteunt deze methode hogere-orde discretisaties (tot P3-P2) en Taylor-Hood elementen, wat essentieel is voor nauwkeurige CFD-simulaties.
3. Monolithische Newton-Krylov-Multigrid Oplosser: Ze presenteren een bewijs van concept voor een monolithische solver die het volledige ruimte-tijd systeem in één keer oplost, gekoppeld aan een Newton-Krylov methode voor de nonlineariteit.
4. Prestatiemodel: Omdat een volledige tijdsparallelle implementatie (met cyclic reduction) op dat moment niet beschikbaar was in de gebruikte software, ontwikkelden de auteurs een gedetailleerd parallel performance model. Dit model voorspelt de snelheidswinsten die haalbaar zijn op toekomstige HPC-systemen met voldoende parallelle middelen.

4. Resultaten

De auteurs testten de methode op twee modelproblemen: de warmtevergelijking en de Navier-Stokes-vergelijkingen (Chorin-test en lid-driven cavity).

• Warmtevergelijking:
  • De WRMG-oplosser toonde schaalbaarheid voor verschillende discretisatieordes (ruimtelijk en tijdelijk).
  • Vergelijking met directe oplossers (LU-factrisatie) en klassiek timestepping: WRMG was aanzienlijk sneller dan directe oplossers voor hogere-orde problemen en toonde goede algoritmische schaalbaarheid, hoewel klassiek timestepping in de huidige (sequentiële in tijd) implementatie nog sneller was voor de geteste probleemgroottes.
• Navier-Stokes (Chorin en Lid-Driven Cavity):
  • De Newton-Krylov-multigrid solver convergeerde robuust voor Reynolds-getallen tot 100.
  • Iteraties: Het aantal Newton-iteraties en FGMRES-iteraties bleef stabiel over verschillende roostergroottes en tijdstappen.
  • Tijdsprestaties: In de huidige implementatie (zonder tijdsparallelisme) was timestepping ongeveer 5 tot 20 keer sneller dan de monolithische WRMG-aanpak. Dit komt door de extra werklast van het oplossen van het volledige ruimte-tijd systeem in één keer en de overhead van het heropbouwen van preconditioners bij niet-lineaire problemen.
  • Geheugen: De monolithische aanpak vereist meer geheugen, maar bleef binnen de limieten van de geteste systemen (tot ~1 miljard niet-nul elementen).

5. Betekenis en Toekomstperspectief

• Potentieel voor Tijdsparallelisme: De kernboodschap is dat de huidige "sequentiële in tijd" implementatie van WRMG nog niet concurrerend is met timestepping voor kleine tot middelgrote problemen. Echter, het ontwikkelde performance model voorspelt dat bij voldoende parallelle middelen (specifiek door het gebruik van cyclic reduction om de tijdrichting te paralleliseren), de WRMG-methode aanzienlijke snelheidswinsten kan bieden (tot 40x voor lage-orde en 12x voor hoge-orde problemen).
• Overcoming Strong Scaling Limits: De methode biedt een oplossing voor het probleem waarbij ruimtelijke parallelisatie verzadigt. Door de tijdrichting ook te paralleliseren, kan men problemen oplossen die te groot zijn voor pure ruimtelijke parallelisatie.
• Toekomstig Werk: De auteurs benadrukken dat de volgende stap het implementeren van een echte tijdsparallelle versie (met cyclic reduction) is. Dit zou een eerlijke vergelijking mogelijk maken met standaard timestepping en andere tijdsparallelle methoden. Daarnaast wordt de uitbreiding naar 3D-vloeistofstromen en adaptiviteit in zowel ruimte als tijd genoemd als belangrijke toekomstige doelen.

Conclusie: Het artikel levert een solide theoretische en numerieke basis voor het gebruik van waveform relaxation multigrid voor complexe vloeistofstromen. Hoewel de huidige implementatie nog niet de snelheid van timestepping evenaart zonder tijdsparallelisme, toont het model aan dat deze methode een veelbelovende richting is voor toekomstige exascale-computing toepassingen waar traditionele methoden vastlopen.