Efficiëntie van micro-macro acceleratie voor stochastische differentiaalvergelijkingen met een tijdschaal scheiding

Hannes Vandecasteele Przemyslaw Zielinkski
In veel wetenschappelijke toepassingen beïnvloeden de microscopische deeltjes, bijvoorbeeld moleculen in de lucht, belangrijke macroscopische grootheden, bijvoorbeeld de luchtdruk en de windsnelheid. Experimenten uitvoeren in dergelijke situaties is vaak zeer moeilijk waardoor we gebruik moeten maken van computersimulaties. Dergelijke computeralgoritmes duren echter zeer lang om een oplossing te berekenen omdat we alle interacties en bewegingen van de moleculen in rekening moeten brengen. In deze scriptie toonden we via veel computerexperimenten aan dat een nieuw algoritme sneller nauwkeurige resultaten kan uitrekenen.

Computer zoomt wiskundig in op microscopische details in virtuele experimenten

Wat hebben de vervorming van plastic, tumorgroei en filevorming met elkaar gemeen? Meer dan je zou denken! Het zijn alle drie fenomenen die we nog niet volledig begrijpen, en waarvoor experimenteren moeilijk ligt. Bovendien is het gedrag dat wij waarnemen het netto-effect van heel veel microscopische interacties. Plastic bestaat uit grote aantallen atomen die met elkaar verbonden worden tot een complex netwerk met een gewenste stevigheid en vervormbaarheid. Een tumor wordt gevormd door een enorme hoeveelheid individuele tumorcellen. Een file ontstaat door de interacties tussen grote aantallen individuele voertuigen. Kan de wiskunde die gemeenschappelijke structuur uitbuiten om tegelijk vooruitgang te boeken in al deze zeer verschillende domeinen?

Experimenten vervangen door computersimulatie

Zowel voor de vervorming van plastic als voor tumorgroei en filevorming is het niet vanzelfsprekend om experimenten uit te voeren. Bij plastic kan experimenteren nog wel, tenminste als het materiaal al bestaat. Alleen is het vaak net de bedoeling te onderzoeken welk materiaal we precies willen maken. Bij tumorgroei kunnen we wel experimenten uitvoeren met groepjes cellen, maar een volledige tumor is heel wat lastiger. En veranderingen aan ons verkeersnetwerk uittesten is simpelweg onmogelijk voordat ze uitgevoerd worden. Experimenten zijn dus heel vaak onpraktisch, en we zijn op zoek naar een alternatieve manier van werken.

Gelukkig komt de wiskunde ons te hulp. Ingenieurs gebruiken wiskundige modellen als een soort krachtige taal die heel precies kan weergeven wat we over een bepaald fenomeen weten. Zo’n modellen worden dan in software gegoten, waarna computers virtuele experimenten kunnen uitvoeren en verschillende scenario’s kunnen doorrekenen. Helaas kennen dat soort computersimulaties hun eigen problemen. In deze scriptie worden enkele van die problemen van dichterbij bekeken.

Beperkingen op de rekenkracht

Computersimulaties zijn enkel nuttig onder twee voorwaarden. Ten eerste moet het virtuele experiment een betrouwbare weergave zijn van wat een echt experiment zou opleveren. Ten tweede mogen de berekeningen niet te lang op zich laten wachten. Voor veel toepassingen zijn die eisen voldaan. Zo wordt computersimulatie routinematig gebruikt bij het ontwerp van auto’s, windturbines en vliegtuigen.

Deze succesvolle toepassingen hebben iets gemeenschappelijk: we beschikken over een nauwkeurig model dat direct geschikt is voor de berekening die we willen uitvoeren. We kunnen rechtstreeks de evolutie van de luchtstroming beschrijven in termen van de windsnelheid, luchtdruk, enzovoort. Ergens is dat bijzonder, want lucht bestaat, microscopisch bekeken, uit grote aantallen moleculen die heel snel rondvliegen en vaak met elkaar botsen. Het zou haast onbegonnen werk zijn om al die moleculen volgen in een computersimulatie op een menselijke schaal. Door naar macroscopische grootheden als windsnelheid en luchtdruk te kijken, kunnen we abstractie maken van de precieze interacties tussen individuele deeltjes. Laat nu net dat hetgeen zijn wat niet kan bij de voorbeelden die we eerder vermeldden...

Nieuwe rekenalgoritmes brengen soelaas

Voor een nauwkeurige beschrijving van het gedrag van plasticEen netwerk van veel atomen zijn we verplicht de precieze verbindingen tussen individuele atomen in rekening te brengen. Bij tumoren moeten we kijken naar het gedrag van individuele cellen. En filevorming wordt heel sterk beïnvloed door individuele bestuurders. Telkens bekijken we interacties tussen grote hoeveelheden individuele deeltjes (atomen, cellen, voertuigen), terwijl we slechts geïnteresseerd zijn in enkele macroscopische grootheden (vervorming, populatiegroei, stromingssnelheid). Die gelijkende structuur kunnen we uitbuiten. Daarvoor bouwen we zelf een abstract “modelprobleem”: een wiskundig model dat bestaat uit niet nader gespecificeerde “deeltjes” en hun interacties, waarvan we precies weten hoe ze zich gedragen. We zorgen ervoor dat ons “modelprobleem” zo eenvoudig mogelijk is, zodat we exact begrijpen hoe het zich gedraagt. Tegelijk moet het modelprobleem de kern van het probleem bevatten dat we in al die verschillende toepassingen tegelijk vaststellen.  Voor ons is die kern de volgende: we willen op een computer de evolutie berekenen van enkele macroscopische grootheden, maar we worden verplicht simulaties uit te voeren met grote hoeveelheden individuele deeltjes.

Eens we een modelprobleem hebben, kunnen we beginnen met het ontwikkelen van nieuwe algoritmes om de computersimulatie uit te voeren. Een algoritme is een precies geformuleerde reeks stappen die de computer vertelt welke berekeningen achtereenvolgens uitgevoerd moeten worden. Wanneer we de computersimulatie willen versnellen, moeten we het simulatie-algoritme veranderen, zodat het dezelfde (of ongeveer dezelfde) oplossing kan bekomen met veel minder rekenwerk. Dat is precies wat we deden voor het probleem van de simulatie van ons veel-deeltjesmodel.

Voorspellen en corrigeren

In de scriptie werkten we met een nieuw algoritme dat in staat is om een de macroscopische evolutie te voorspellen op basis van een korte microscopische simulatie van de deeltjes. Kort door de bocht volgen we een groot aantal deeltjes voor een korte tijdspanne, waarbij we alle individuele interacties in kaart brengen. Concreet kijken we naar een wolk deeltjes die bewegen en botsen, en beperken we de simulatie tot enkele microseconden in fysische tijd. Omdat de computer elk van de vele botsingen apart moet uitrekenen, duren de berekeningen zelfs in dit geval al gauw enkele minuten. Dat lijkt lang, maar is haalbaar. Alleen doet de computer er dan al vlug enkele dagen over om een enkele fysische seconde te overbruggen. Onze methode versnelt de berekeningen door na de korte microscopische simulatie een voorspelling te maken van de plaats van het centrum van die wolk op een later tijdstip. Ná die extrapolatie genereren we dan een nieuwe wolk rond dat centrum. De voornaamste vernieuwing in het algoritme is de manier waarop het algoritme die nieuwe wolk genereert.

Dat zo’n methode een enorme winst in rekentijd kan opleveren, lijkt duidelijk. Maar mogen we het wel gebruiken? Zijn de bekomen simulatieresultaten wel betrouwbaar? Om dat te bekijken voerden we in de scriptie een groot aantal virtuele experimenten uit. Door ons modelprobleem zo te kiezen dat we ook de “juiste” oplossing kennen, konden we heel goed de nauwkeurigheid van ons algoritme inschatten. De resultaten waren zo veelbelovend dat we ze zowel wiskundig wilden bewijzen, als het algoritme in de praktijk wilden brengen voor meer realistische voorbeelden. Dat lukte allebei. De weg ligt dus open om een bijzonder efficiënte en algemeen toepasbare methodiek te ontwikkelen voor de computersimulatie van eender welk veel-deeltjesmodel, of het nu gaat om plastic, een tumor of een verkeersstroom.

 

Bibliografie

Abdulle, Assyr & Cirilli, Stephane (2008). S-ROCK: Chebyshev methods for stiff stochastic differential equations. SIAM Journal on Scientific Computing, 30, 997-1014.

Dimarco, Giacomo & Pareschi, Lorenzo (2014). Numerical methods for kinetic equations. Acta Numerica, 23, 369-520.

Li, Tiejun, Abdulle, Assyr & others (2008). Effectiveness of implicit methods for stiff stochastic differential equations.

Kevrekidis, Ioannis G & Samaey, Giovanni (2009). Equation-free multiscale computation: Algorithms and applications. Annual review of physical chemistry, 60, 321-344.

Debrabant, Kristian, Samaey, Giovanni & Zieliński, Przemysław (2017). A micro-macro acceleration method for the Monte Carlo simulation of stochastic differential equations. SIAM Journal on Numerical Analysis, 55, 2745-2786.

Givon, Dror, Kupferman, Raz & Stuart, Andrew (2004). Extracting macroscopic dynamics: model problems and algorithms. Nonlinearity, 17, R55.

Atkinson, Kendall & Han, Weimin (2005). Theoretical numerical analysis. Springer

Samaey, Giovanni, Lelièvre, Tony & Legat, Vincent (2011). A numerical closure approach for kinetic models of polymeric fluids: exploring closure relations for FENE dumbbells. Computers & Fluids, 43, 119-133.

Pavliotis, Grigoris & Stuart, Andrew (2008). Multiscale methods: averaging and homogenization. Springer Science \& Business Media

Melis, Ward (2017). Projective Integration for Hyperbolic Conservation Laws and Multiscale Kinetic Equations. Phd thesis, Faculty of Engineering Sciences, KU Leuven.

Petersen, Kaare Brandt, Pedersen, Michael Syskind & others (2008). The matrix cookbook. Technical University of Denmark, , .

Lelièvre, Tony, Samaey, Giovanni & Zieliński, Przemysław (2018). Analysis of a micro-macro acceleration method with minimum relative entropy moment matching. arXiv preprint arXiv:1801.01740.

Legoll, Frédéric & Lelièvre, Tony (2010). Effective dynamics using conditional expectations. Nonlinearity, 23, 2131.

Burov, S & Barkai, E (2008). Fractional Langevin equation: Overdamped, underdamped, and critical behaviors. Physical Review E, 78, 031112.

Zagaris, Antonios, Vandekerckhove, Christophe, Gear, C William, Kaper, Tasso J & Kevrekidis, Ioannis G (2012). Stability and stabilization of the constrained runs schemes for equation-free projection to a slow manifold. Discrete and continuous dynamical systems-Series A, 32, 2759-2803.

Ghoos, Kristel, Dekeyser, Wouter, Samaey, Giovanni, Börner, Petra & Baelmans, Martine (2016). Accuracy and convergence of coupled finite-volume/Monte Carlo codes for plasma edge simulations of nuclear fusion reactors. Journal of Computational Physics, 322, 162-182.

Byrne, George D & Hindmarsh, Alan C (1987). Stiff ODE solvers: A review of current and coming attractions. Journal of Computational physics, 70, 1-62.

Burrage, Kevin, Burrage, Pamela & Tian, Tianhai (2004). Numerical methods for strong solutions of stochastic differential equations: an overview. Proceedings of The Royal Society of London A: Mathematical, Physical and Engineering Sciences, 460, 373-402.

Abdulle, Assyr & Cirilli, Stéphane (2007). Stabilized methods for stiff stochastic systems. Comptes Rendus Mathematique, 345, 593-598.

Komori, Yoshio & Burrage, Kevin (2012). Weak second order S-ROCK methods for Stratonovich stochastic differential equations. Journal of Computational and Applied Mathematics, 236, 2895-2908.

Chalub, Fabio, Dolak-Struss, Yasmin, Markowich, Peter, Oelz, Dietmar, Schmeiser, Christian & Soreff, Alexander (2006). Model hierarchies for cell aggregation by chemotaxis. Mathematical Models and Methods in Applied Sciences, 16, 1173-1197.

Kevrekidis, Ioannis G & Kevrekidis, Panagiotis G (2003). Equation-free, coarse-grained multiscale computation: Enabling mocroscopic simulators to perform system-level analysis. Communications in Mathematical Sciences, 1, 715-762.

Abdulle, Assyr, E, Weinan, Engquist, Björn & Vanden-Eijnden, Eric (2012). The heterogeneous multiscale method. Acta Numerica, 21, 1-87.

Bruna, Maria, Chapman, S Jonathan & Smith, Matthew J (2014). Model reduction for slow--fast stochastic systems with metastable behaviour. The Journal of chemical physics, 140, 174107.

Komori, Yoshio & Burrage, Kevin (2013). Strong first order S-ROCK methods for stochastic differential equations. Journal of Computational and Applied Mathematics, 242, 261-274.

Masmoudi, Nader (2008). Well-posedness for the FENE dumbbell model of polymeric flows. Communications on Pure and Applied Mathematics, 61, 1685-1714.

Debrabant, Kristian, Samaey, Giovanni & Zieliński, Przemysław (2018). Study of micro-macro acceleration schemes for linear slow-fast stochastic differential equations with additive noise. arXiv:1805.10219.

Wright, Stephen & Nocedal, Jorge (1999). Numerical optimization. Springer Science, 35, 7.

Jaynes, Edwin T (2003). Probability theory: the logic of science. Cambridge university press

Gardiner, Crispin (2009). Stochastic methods. springer Berlin

Kapur, Jagat Narain & Kesavan, Hiremaglur K (1992). Entropy optimization principles and their applications. , 3-20.

Ebeling, Werner & Romanovsky, M Yu (2009). Microfields, Kinetic Equations and Fusion Rates in Exploding Ion Clusters. Contributions to Plasma Physics, 49, 477-487.

Saito, Yoshihiro & Mitsui, Taketomo (1996). Stability analysis of numerical schemes for stochastic differential equations. SIAM Journal on Numerical Analysis, 33, 2254-2267.

Hershey, John R & Olsen, Peder A (2007). Approximating the Kullback Leibler divergence between Gaussian mixture models. , 4, IV-317.

Yeh, Shi-Tao & others (2002). Using trapezoidal rule for the area under a curve calculation. Proceedings of the 27th Annual SAS User Group International (SUGI02), , .

Universiteit of Hogeschool
Master of Science in de Ingenieurswetenschappen
Publicatiejaar
2018
Promotor(en)
Giovanni Samaey
Kernwoorden
@Hannes_vdc
Deel deze scriptie