Practicum Computational Science

In numerieke simulaties staat vaak het oplossen van grote stelsels lineaire vergelijkingen centraal. In deze cursus wordt de stroming van grondwater en de verspreiding van verontreinigingen in grondwater gesimuleerd. De technieken die de revu passeren en de inzichten die hierbij opgedaan zullen worden zijn echter ook toepasbaar bij het numeriek simuleren van diverse andere fysische verschijnselen.

Stelsels van lineaire vergelijkingen ontstaan door discretisatie van de partiële differentiaalvergelijkingen (PDV) die de stroming en de verspreiding wiskundig beschrijven. De stelsel zullen zeer groot zijn als een hoog oplossend vermogen, d.w.z. een grote nauwkeurigheid, van het numerieke model, verlangd wordt. Een miljoen vergelijkingen met evenzoveel onbekenden vormt geen uitzondering. De stelsels vergelijkingen zijn vanuit een wiskundig standpunt eenvoudig. Toch zijn ze in numerieke simulaties door hun grootte vrijwel altijd de bottleneck: meer dan 90% van de totale rekentijd gaat in het oplossen ervan zitten. In deze cursus concentreren we ons daarom voornamelijk op het numeriek oplossen van deze stelsels.

De stelsels worden gerepresenteerd als matrix-vector vergelijkingen. De matrices hebben een bepaalde "ijlheidsstructuur". Directe methoden (die vrijwel allemaal op Gauss elimenatie gebaseerd zijn) kunnen deze ijlheid maar in beperkt mate uitbuiten. Iteratieve methoden kunnen dat wel. Ze zijn daardoor efficiënt. En in feite zijn ze onontbeerlijk. Voor een goede `performance' moeten een aantal keuzes gemaakt worden (methode, parameters, preconditioneerder, implementatie, etc.). Voor een optimale tuning is echter niet alleen expertise nodig in iteratieve methoden, maar ook in het onderliggend fysisch probleem, het wiskundig model, de discretisatie en de architectuur van de computer.

Aspecten die aan de orde komen:
  - wiskundige modelleren van de grondwaterstronig,
  - discretiseren van de resulterende PDV (een advectie-diffusie vergelijking),
  - formuleren als matrix-vector vergelijking,
  - iteratief oplossen (Geconjugeerde Gradiënten en generaliseringen als BiCGSTAB),
  - versnellen van het oplosproces middels preconditionering (verschillende incomplete LU-decomposities).
Alle stappen worden geïmplementeerd en getest op efficiëntie en nauwkeurigheid.

Keywords: advectie-diffusie vergelijk, gemengde randvoorwaarden, eindige differenties, row-indexed compact storage, GCR, genestte iteratieve methoden, CG, BiCGSTAB, ILU, MILU, RILU, Eisenstat truck, BLAS

- Opbouwen van een zekere theoretische maar vooral practische expertise in het iteratief oplossen van grote stelsels lineaire vergelijkingen die bijvoorbeeld ontstaan bij discretisatie van partiële differentiaalvergelijkingen.

- Kennismaken met alle facetten van numerieke simulatie van grondwaterstromingen en van verschijnselen die leiden tot een vergelijkbaar wiskundig model.

Er wordt programmatuur ontwikkeld (in C++) voor numeriek simulatie van grondwaterstroming en verspreiding van verontreinigingen. De code wordt getest op efficiëntie en betrouwbaarheid.

Aanvankelijk wordt individueel gewerkt, later in teams van twee à drie personen.

De cursus wordt gegeven in een computerruimte. Het geleerde kan onmiddellijk in de praktijk uitgevoerd en getest worden.

De cursus is een mengvorm van college, werkcollege en computerpracticum.
Als je deelneemt is er een aanwezigheidsplicht. Kan je een keer echt niet, geef dat dan tijdig door aan de docent. Een klassikale uitleg kan dan eventueel op een ander tijdstip gepland worden.

Het schrijven van het verslag is het meest tijdrovende deel van de cursus.

Er zitten 60 ECTS in een jaar. Dat impliceert dat je voor een cursus van 7.5 ECTS verondersteld wordt wekelijks 20 uur te besteden gedurende 9 weken. Voor deze cursus Computational Science zijn er 8 a 10 klassikale bijeenkomsten van 4 uur. Werk je thuis ook nog 2 a 4 uur per bijeenkomst aan de cursus, dan blijft er nog 100 a 140 uur werk over. Dat is de tijd die je verondersteld wordt aan experimenten te besteden en het schrijven van het verslag.

Iteratieve methoden voor lineaire vergelijkingen worden ook behandeld in het college Numerieke Lineaire Algebra (WISM451, WISB351, NUM3). De behandeling daar is theoretischer. Het college en dit practicum vullen elkaar uitstekend aan en gelijktijdig volgen leidt tot beter begrip. Beide cursussen kunnen echter ook onafhankelijk van elkaar gevolgd worden.

Er wordt geprogrammeerd in C++. Een deel van de code is echter beschikbaar en dat is voldoende om ook zonder C++ ervaring snel voldoende vaardigheid in C++ programmeren op te pikken. Er wordt niet geprogrammeerd in Matlab, maar soms is Matlab handig om de ontwikkelde programma's te testen.

Schrijf je tijdig in voor de cursus (via OSIRIS). Als je niet ingeschreven bent heb je tijdens de cursus geen toegang tot de computers. Schaf tijdig bij het secretariaat Wiskunde de practicumhandleiding (diktaat) aan en bestudeer het theoretisch deel van te voren (bestudeer voor de eerste bijeenkomst tot Sektie 3.1.

In het verslag moet met name ingegaan worden op de effectiviteit van de diverse keuzes. De numerieke experimenten in het verslag mogen niet slechts illustratief zijn, maar dienen de argumentatie te ondersteunen. Uit het verslag moet een kritische houding blijken. Een verslag mag samen met teamgenoten geschreven worden. Individuele bijdragen moeten echter herkenbaar zijn en iedere auteur is aanspreekbaar over het geheel. Het verslag wordt individueel nabesproken. De toelichting die daarbij gevraagd kan worden, beïnvoedt het eindcijfer. (Hier vind je meer aanwijzingen bij het schrijven van het verslag.)

Het verslag wordt nabesproken. Bij een onvoldoende kunnen de nieuwe inzichten in het verslag verwerkt worden en het verslag kan dan opnieuw (samen met de originele versie) ingeleverd worden. Het eindcijfer is dan (2*C2+C1)/3, waarbij C1 het cijfer is voor het oorspronkelijke verslag en C2 voor de herziene versie.

Een practicumhandleiding/diktaat kan gekocht worden bij het secretariaat Wiskunde. Een deel van de code voor met name de eerste paar bijeenkomsten is electronisch beschikbaar. Verder wordt er achtergrond literatuur uitgedeeld of via internet beschikbaar gesteld.

• Practicumhandleiding/diktaat
  Computational Science Practicum; Iteratieve Lineaire Oplosmethoden, door Gerard L.G. Sleijpen   (.pdf 426Kb, .ps.gz 378Kb, .tex (.tar.gz 84Kb  *))
  Listing van de C++ code (startpakket)   (.pdf 22Kb, .ps.gz 15Kb)
• Code (startpakket)
  • C++ files   (.tar.gz 6Kb  *)
• Achtergrondmateriaal
  • Over iteratieve methoden
    • Krylov subspave methods for linear systems of equations, by Gerard L.G. Sleijpen and (Preprint, 1993)   (.ps.gz  190Kb)
    • Templates for the solution of linear systems; building blocks for iterative methods, by Richard Barrett, Michael Berry, Tony F. Chan, James Demmel, June Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo, Charles Romine, ,   (lokaal .ps (.tar.gz  337Kb  *))
    • Numerieke Wiskunde 3, Dictaat Numerieke Lineaire Algebra, door   (.ps.gz , 212Kb)
    • Lecture Notes on Iterative Methods, by ,   pp.1-72 (.ps.gz , 259Kb),   pp. 73-133 (.ps.gz , 214Kb),   pp.134-197 (.ps.gz , 241Kb)
    • Numerical Recipes, Chaper 2.7, Sparse linear systems
  • Sparse storage formats:
    Numerical Recipes, Indexed storage of sparse matrices, p.78-83
  • C++ Code
    • Numerical Recipes C++ code als afgedrukt in het boek (lokaal .tar.gz  104Kb  *)
    • Templates, bicg, bicgstab, cg, cgs, cheby, gmres, ir, qmr   (lokaal .tar.gz  4Kb  *)
  • Online handleiding matlab (we gebruiken matlab voor de grafische uitvoer en om de pragramma's gemakkelijk te kunnen testen)
  • Over C++ programmeren
    • C++ Programming, by Sharam Hekmat
    • C++ tutorial, by Ivor Horton
    • C++ User's Guide, from SUN

Hier (beperkte toegankelijkheid) vind je plaatjes van oplossingen van een paar testproblemen uit de practicumhandleiding.

Het past beter bij het vak (een "doe vak") om er intensief mee bezig te zijn (in een kortere tijd). Het vak wordt daarom geven in twee dagdelen per week gedurende vier weken. In de overige vier weken (en de tentamenweek) van de periode zijn er geen cursusbijeenkomsten meer, maar werk je aan de experimenten en aan het verslag. Uiteraard kan je altijd met vragen terecht bij de docent.

In principe wordt de benodigde theorie uitgelegd tijdens het practicum. De huidige groep deelnemers is echter groot (te groot voor 1 computerzaal) en het is daarom handiger om de theoretische inleiding (pm 60 min) klassikaal te doen. In het Minneart Gebouw is op maandag en woensdag om 13:15 zaal 202 gereserveerd. Daarna is het practisch deel. Dat is in de computerzalen van het wiskunde gebouw.

Waar:
    Theoretische inleiding in het Minneart Gebouw, zaal 202
    Practische uitwerking in het Wiskunde Gebouw, zaal 510 (en 509)
Wanneer: 4de periode,
    maandags van 13u00-17u00 en
    woensdags van 13u00-17u00.
Eerste bijeenkomst:
    woensdag 22 april, 13:15 in zaal 202 van het Minneart Gebouw.
Behandeld:

Week 1: tot en met sektie 4.