Print deze pagina 21 december 2004 2004/11

Recycling van weggegooide numerieke informatie

Verbetering van succesvolle rekenmethode
Computersimulaties worden gebruikt om de eigenschappen van nieuwe materialen te voorspellen. De eerste simulaties werden ruim vijftig jaar geleden uitgevoerd door Nicholas Metropolis en collega's verbonden aan het Los Alamos National Laboratory in de Verenigde Staten. De rekenmethode die zij in 1953 ontwikkelden (de zogeheten Metropolis Monte Carlo-methode) was zo succesvol dat aan de kern van het gebruikte rekenschema in de afgelopen 50 jaar niets is veranderd. De Metropolis-methode wordt niet alleen gebruikt voor fysische berekeningen, maar ook in economische modellen en theoretische genetica. In de editie van 21 december 2004 van de Proceedings of the National Academy of Science (PNAS) in Washington suggereert Daan Frenkel, verbonden aan het FOM-Instituut voor Atoom- en Molecuulfysica in Amsterdam, dat de efficiëntie van de oorspronkelijke Metropolis Monte Carlo-methode kan worden verbeterd, zeker wanneer een groot aantal rekenstappen parallel kan worden uitgevoerd.

De Monte Carlo-methode ontleent zijn naam aan het feit dat in dit rekenschema, gebruik wordt gemaakt van toevalsgetallen, om precies te zijn: getallen die een willekeurige waarden hebben tussen nul en één. Hoe werkt die methode? Dat is het best uit te leggen aan de hand van een eenvoudig voorbeeld: de verdeling van konijnen over twee aangrenzende natuurgebieden met de prozaïsche namen A en B. Met gewone kansberekening geldt de volgende redenering. De gebieden hebben oppervlakken O_A en O_B . De konijnen dragen zendertjes waarmee ze informatie kunnen leveren over de plek waar ze zich bevinden (bijvoorbeeld over de temperatuur). Als A en B even aantrekkelijk zijn voor konijnen, dan is de kans om een willekeurig konijn aan te treffen in gebied A gelijk aan O_A /(O_A+O_B). We noemen deze kans P_A. De kans P_B om een konijn aan te treffen in gebied B is dan gelijk aan 1-P_A. We zouden de gemiddelde temperatuur in de parken kunnen bepalen door één enkel konijn gedurende een lange tijd op zijn omzwervingen de temperatuur te laten meten. Dat kan echter inefficiënt zijn, bijvoorbeeld als de parken gescheiden zijn door een hek waar maar één klein gaatje in zit.

De Monte Carlo-methode werkt anders: we zetten een konijn in één van de twee parken (bijvoorbeeld A) en dan doen we een zogeheten "test-verplaatsing" naar B. Als P_B groter is dan P_A, accepteren we de verplaatsing en het konijn verhuist naar B. Als P_A echter groter is dan P_B, dan kiezen we een toevalsgetal tussen nul en één. Als dat getal kleiner is dan de verhouding P_B/P_A, dan wordt het konijn in B geplaatst. Anders blijft het in A. Daarna doen we, vanuit de nieuwe situatie, weer een test-verplaatsing van het konijn, enzovoorts. Op die manier worden de parken A en B met de correcte waarschijnlijkheid bezocht. Nu komt het vreemde van de Metropolis-methode: na iedere poging tot verplaatsing, meet het konijn de temperatuur, ook al is de poging verworpen en bevindt het konijn zich nog steeds op dezelfde plek als na de vorige test-verplaatsing. In dat geval wordt alle informatie over de test-verplaatsing weggegooid.

In de praktijk gaat het bij Monte Carlo-simulaties niet om een systeem met slechts twee toestanden, maar met een astronomisch groot aantal. Zolang we de relatieve waarschijnlijkheid van ieder paar toestanden kunnen uitrekenen, kunnen we het Metropolis Monte Carlo-schema toepassen. Steeds geldt evenwel: informatie over verworpen test-verplaatsingen wordt weggegooid.

De suggestie van Frenkel is nu om die weggegooide informatie wel te gebruiken, zonder de Monte Carlo-aanpak zelf geweld aan te doen. Voor een gewone Monte Carlo-berekening levert deze suggestie slechts beperkte winst op, maar voor berekeningen waarin een groot aantal test-verplaatsingen parallel kan worden uitgevoerd, kan de winst zeer aanzienlijk zijn. De reden is de volgende: stel dat er N test-verplaatsingen parallel worden uitgevoerd. Iedere verplaatsing kan worden geaccepteerd of verworpen. Normaal behouden we slechts de informatie over één eindtoestand, de informatie over de resterende 2^N – 1 "verworpen" toestanden wordt weggegooid. In het nieuwe schema wordt deze informatie behouden. De uitkomst wordt daarmee nauwkeuriger. De temperatuursmetingen uit de tweede alinea bijvoorbeeld zijn nu immers gebaseerd op een veel groter aantal metingen.

Momenteel wordt de methode op AMOLF toegepast bij het bestuderen van het gedrag van colloïden en modeleiwitten.

Meer informatie bij prof.dr. D. Frenkel, telefoon (020) 608 12 34.

Bron:
D. Frenkel, Speed-up of Monte Carlo simulations by sampling of rejected states, Proc. Nat. Acad. Sci. USA, 101, 17571-17575 (2004).