Een parallelle multilevel Monte-Carlomethode voor de simulatie van stochastische partiële differentiaalvergelijkingen
Uncertainty Quantification: de volgende grote uitdaging voor de industrie?
Pieterjan Robbe
Hoelang duurt het vooraleer grondwater vanuit een ondergrondse opslagplaats voor radioactief afval de buitenlucht bereikt? Het radioactieve grondwater sijpelt immers langzaam doorheen de rotswand die de opslagplaats omringt. Het antwoord op deze vraag hangt af van verschillende factoren: de soort en de eigenschappen van de rots, de dikte, het drukverschil tussen opslagplaats en omgeving… Modellen voor complexe processen, zoals bovenstaand probleem, zijn slechts een benadering en dus inherent onzeker. Hoe men met deze onzekerheid moet omgaan en wat het effect is op de output is een actuele onderzoeksvraag, en eveneens het onderwerp van deze scriptie.
Onzekerheidskwantificatie
Klassiek wordt een ontwerpproces opgedeeld in drie grote stappen. Eerst wordt het reële systeem vereenvoudigd tot een wiskundig model. Daarna wordt het model omgezet in een computermodel, dat kan worden gesimuleerd. De hoop is dan dat het computermodel zich gedraagt als het werkelijke systeem. Hoe goed het model de werkelijkheid benadert kan tot slot worden nagegaan aan de hand van experimenten in de echte wereld. Het ontwerpproces wordt aangevuld met een terugkoppeling: wanneer tijdens simulaties of experimenten blijkt dat het model de werkelijkheid niet voldoende benadert, wordt een verdere verfijning aan het model aangebracht.
Modellering, simulatie en experimenten worden ook wel de drie pijlers van de moderne wetenschap en technologie genoemd. Hoe een model zich gedraagt bij een onzekere input blijft echter nog een belangrijk open vraagstuk. Wanneer de input van een model onzeker is, zal immers ook de output onderhevig zijn aan een bepaalde onzekerheid. Bronnen voor deze onzekerheid kunnen vaag gespecificeerde of willekeurig variërende modelparameters zijn, alsook de geometrie van een probleem, de omgevingsfactoren of bepaalde materiaaleigenschappen. Bovendien is elk model slechts een benadering van de werkelijkheid. Numerieke afrondingsfouten in de simulaties en fouten in de gebruikte experimenten voor modelkalibratie zorgen voor bijkomende onzekerheden. De wetenschap die zich bezig houdt met het rigoureus identificeren, kwantificeren en reduceren van de onzekerheid in deze drie pijlers noemt men onzekerheidskwantificatie (Uncertainty Quantification).
Monte-Carlosimulatie
Een mogelijke techniek om de onzekerheden op de output van een model te bepalen is de Monte-Carlomethode (MC). In de klassieke Monte-Carlomethode wordt verschillende keren een oplossing berekend voor verschillende willekeurige realisaties van de onzekere modelparameters. Voor elke realisatie wordt dan een deterministisch probleem (zonder onzekerheid) opgelost. Nadien worden de, vaak vele duizenden tot zelfs miljoenen, deterministische problemen gecombineerd tot een beschrijving van de onzekerheden in het model. Het grootste nadeel van deze methode is de snelheid: er zijn zéér veel realisaties nodig om de oplossing voldoende nauwkeurig te berekenen.
In de praktijk beschouwt men vaak modellen beschreven door partiële differentiaalvergelijkingen of PDEs. Deze vergelijkingen worden wiskundig opgelost door de geometrie te benaderen door een rooster van punten, ook wel mesh genoemd. Voor een gegeven realisatie van de modelparameters wordt de oplossing van de PDE dan gezocht in al deze punten. Hoe meer punten in het rooster, hoe nauwkeuriger de oplossing, maar ook hoe duurder één deterministische oplossing wordt.
Een recente methode voor het kwantificeren van de onzekerheid in modellen is de Multi-Level Monte-Carlomethode (MLMC). Dit multilevelalgoritme combineert Monte-Carlosimulatie met een opeenvolging van roosters met steeds toenemende nauwkeurigheid. Deze roosters noemt men ook wel levels. Het doel van de methode is om het aantal realisaties op de nauwkeurige (maar dure) roosters te verminderen.
Koffiepauze
Deze scriptie onderzoekt hoe de MLMC-methode verder kan worden verbeterd door welgekozen realisaties van de modelparameters te gebruiken, in plaats van de willekeurige realisaties in de Monte-Carlomethode. Numerieke simulaties met deze nieuwe methode tonen duidelijk de superioriteit ten opzichte van de bestaande methoden. Zo kan voor een bepaald probleem de rekentijd worden teruggebracht van vier maanden met de Monte-Carlomethode, tot nauwelijks een half uur met de nieuwe methode. Dat is de gemiddelde tijd die een onderzoeker besteedt aan een koffiepauze, en dus ook de tijd die hij wil wachten tot de simulatie afgelopen is.
Onzekerheidskwantificatie wordt in de toekomst dus steeds belangrijker. De toegenomen rekenkracht van de computer maakt het mogelijk om ook voor complexe systemen een groot aantal deterministische realisaties te berekenen. Dat laat dan toe om het effect van de onzekerheden in het complex model te kwantificeren. Een volgende stap is dan de optimale aansturing van het systeem. Wat is, gegeven een maximale kost, de optimale dikte van de rotswand? Welk materiaal is het meest geschikt? Kan men, door het aanleggen van een bepaalde druk van buitenaf, de uitstroom van radioactief grondwater verminderen? Marcus Meyer, ingenieur bij Rolls Royce verwoordt het als volgt: “Optimization under uncertainties is the next big scientific challenge”.
Bibliografie
[1] A. Barth, C. Schwab, en N. Zollinger. Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients. Numerische Mathematik, 119(1):123–161, 2011.
[2] R. H. Bisseling. Parallel Scientific Computation: A structured approach using BSP and MPI. Oxford University Press, Oxford, 2004.
[3] W. L. Briggs en S. F. McCormick. A multigrid tutorial. SIAM publications, Philadelphia, 2000.
[4] S. Burgos en M. B. Giles. Computing Greeks using multilevel path simulation. In Monte Carlo and Quasi-Monte Carlo Methods 2010, paina’s 281–296. Springer, New York, 2012.
[5] R. E. Caflisch. Monte Carlo and quasi-Monte Carlo methods. Acta Numerica, 7:1–49, 1998.
[6] C. Canuto. Multilevel Monte Carlo method for PDEs with fluid dynamic ap- plications. PhD thesis, King Abdullah University of Science and Technology, Turin, 2014.
[7] J. Charrier, R. Scheichl, en A. L. Teckentrup. Finite element error analysis of elliptic PDEs with random coefficients and its application to multilevel Monte Carlo methods. SIAM Journal on Numerical Analysis, 51(1):322–352, 2013.
[8] K. Cliffe, M. Giles, R. Scheichl, en A. L. Teckentrup. Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients. Computing and Visualization in Science, 14(1):3–15, 2011.
[9] N. Collier, A.-L. Haji-Ali, F. Nobile, E. von Schwerin, en R. Tempone. A continuation multilevel Monte Carlo algorithm. BIT Numerical Mathematics, paina’s 1–34, 2014.
[10] P. Constantine. A primer on stochastic Galerkin methods, Lecture Notes, 2007. http://inside.mines.edu/~pconstan/docs/constantine-primer.pdf. Online, geraadpleegd op 20 december 2014.
[11] B. Debusschere. Polynomial Chaos based uncertainty propagation. Slides, 4 lectures, mei 2013. KU Leuven Summer School on Uncertainty Quantification, http://people.cs.kuleuven.be/~dirk.nuyens/uqss2013/. Online, geraadpleegd op 14 september 2014.
[12] J. Dick, F. Kuo, Q. T. L. Gia, en C. Schwab. Multi-level higher order QMC Galerkin discretization for affine parametric operator equations. arXiv preprint arXiv:1406.4432, 2014.
[13] J. Dick, F. Y. Kuo, Q. T. Le Gia, D. Nuyens, en C. Schwab. Higher order QMC Petrov–Galerkin Discretization for Affine Parametric Operator Equations with Random Field Inputs. SIAM Journal on Numerical Analysis, 52(6):2676–2702, 2014.
[14] J. Dick, F. Y. Kuo, en I. H. Sloan. High-dimensional integration: the quasi-Monte Carlo way. Acta Numerica, 22:133–288, 2013.
[15] R. W. Fox, A. T. McDonald, en P. J. Pritchard. Introduction to fluid mechanics, volume 5. John Wiley & Sons, New York, 1998.
[16] R. G. Ghanem en P. D. Spanos. Stochastic finite elements: a spectral approach. Courier Corporation, Chelmsford, Massachusetts, 2003.
[17] M. B. Giles. Multilevel Monte Carlo Path Simulation. Operations Research, 56(3):607–617, 2008.
[18] M. B. Giles. Monte Carlo Methods for Uncertainty Quantification. Slides, 4 lectures, mei 2013. KU Leuven Summer School on Uncertainty Quantification, http://people.maths.ox.ac.uk/~gilesm/mc2013/. Online, geraadpleegd op 20 augustus 2014.
[19] M. B. Giles en L. Szpruch. Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation. The Annals of Applied Probability, 24(4):1585–1620, 2014.
[20] M. B. Giles en B. J. Waterhouse. Multilevel quasi-Monte Carlo path simulation. Advanced Financial Modelling, Radon Series on Computational and Applied Mathematics, 8(1):165–181, 2009.
[21] I. G. Graham, F. Y. Kuo, D. Nuyens, R. Scheichl, en I. H. Sloan. Quasi-Monte Carlo methods for elliptic PDEs with random coefficients and applications. Journal of Computational Physics, 230(10):3668–3694, 2011.
[22] S. Heinrich. Multilevel Monte Carlo methods. In I. Lirkov, S. D. Margenov, en J. Wasniewski, editors, Large-scale scientific computing, pagina’s 58–67. Springer, Berlin, Heidelberg, 2001.
[23] A. Iserles. A first course in the numerical analysis of differential equations. Cambridge University Press, Cambridge, 2009.
[24] A. Kebaier. Statistical Romberg extrapolation: a new variance reduction method and applications to option pricing. The Annals of Applied Probability, 15(4):2681–2705, 2005.
[25] D. Kosambi. Statistics in function space. J. Indian Math. Soc, 7(1):76–88, 1943.
[26] F. Y. Kuo. Lattice rule generating vectors, 2007. http://web.maths.unsw.
edu.au/~fkuo/lattice/index.html. Online, geraadpleegd op 5 februari 2015.
[27] F. Y. Kuo, C. Schwab, en I. H. Sloan. Quasi-Monte Carlo methods for high- dimensional integration: the standard (weighted Hilbert space) setting and beyond. The ANZIAM Journal, 53(1):1–37, 2011.
[28] F. Y. Kuo, C. Schwab, en I. H. Sloan. Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients. SIAM Journal on Numerical Analysis, 50(6):3351–3374, 2012.
[29] F. Y. Kuo, C. Schwab, en I. H. Sloan. Multi-level Quasi-Monte Carlo Fi- nite Element Methods for a Class of Elliptic PDEs with Random Coefficients. Foundations of Computational Mathematics, 15(2):1–39, April 2015.
[30] F. Y. Kuo en I. H. Sloan. Lifting the curse of dimensionality. Notices of the AMS, 52(11):1320–1328, 2005.
[31] H. W. Lilliefors. On the Kolmogorov-Smirnov test for normality with mean and variance unknown. Journal of the American Statistical Association, 62(318):399– 402, 1967.
[32] P. Longley. Geographic information systems and science. John Wiley & Sons, New York, 2005.
[33] N. Metropolis. The beginning of the Monte Carlo method. Los Alamos Science, 15(584):125–130, 1987.
[34] R. E. Moore en M. J. Cloud. Computational Functional Analysis. Elsevier, Amsterdam, 2007.
[35] K. W. Morton en D. F. Mayers. Numerical solution of partial differential equations: an introduction. Cambridge University Press, Cambridge, 2005.
[36] D. Nuyens. The magic point shop of qmc point generators and generating vectors, 2010. http://people.cs.kuleuven.be/dirk.nuyens/qmc-generators/. Online, geraadpleegd op 15 december 2014.
[37] D. Nuyens. Fast construction of good lattice rules. PhD thesis, KU Leuven, Leuven, 2007. https://lirias.kuleuven.be/handle/1979/860. Online, geraadpleegd op 12 februari 2014.
[38] A. Teckentrup, R. Scheichl, M. Giles, en E. Ullmann. Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients. Numerische Mathematik, 125(3):569–600, 2013.
[39] A. L. Teckentrup. Multilevel Monte Carlo methods and uncertainty quantification. PhD thesis, University of Bath, 2013. http://opus.bath.ac.uk/36651/1/ UnivBath_PhD_2013_A_Teckentrup.pdf. Online, geraadpleegd op 10 oktober 2014.
[40] S. Torquato. Random heterogeneous materials: microstructure and macroscopic properties, volume 16. Springer Science & Business Media, New York, 2002.
[41] B. Tuffin. Randomization of Quasi-Monte Carlo Methods for Error Estimation: Survey and Normal Approximation. Monte Carlo Methods and Applications, 10(3-4):617–628, 2004.
