Discrete empirische interpolatiemethode (DEIM)
Stel je voor dat je het weer voor heel Nederland wilt voorspellen. In theorie zou je op elke vierkante meter een sensor kunnen zetten en alle metingen doorrekenen, maar dat is onbetaalbaar traag. In de praktijk kiezen meteorologen een beperkt aantal goed gekozen weerstations, en met slimme wiskundige modellen wordt daaruit het volledige beeld gereconstrueerd. De discrete empirische interpolatiemethode, meestal afgekort tot DEIM, doet iets vergelijkbaars, maar dan binnen computersimulaties van bijvoorbeeld motoren, vliegtuigvleugels, hersencellen of ondergrondse waterstromen.
Grote technische simulaties bestaan vaak uit miljoenen rekenpunten die elk een klein stukje van de werkelijkheid vertegenwoordigen. Als de fysica niet-lineair is — dat wil zeggen: de uitkomst verandert niet recht evenredig met de invoer, zoals bij turbulentie, chemische reacties of zenuwsignalen — dan moet een computer die niet-lineaire berekening telkens opnieuw uitvoeren op al die miljoenen punten. DEIM is een wiskundige truc die dat aantal rekenpunten drastisch verkleint, door van tevoren te bepalen welke handvol punten het meest informatief zijn, en de rest van het antwoord daaruit af te leiden. Het resultaat: simulaties die honderden tot duizenden keren sneller kunnen draaien, met een nauwkeurigheid die vaak verrassend dicht bij het volledige model blijft.
Wat is het precies?
Om DEIM te begrijpen, moet je eerst weten wat model-orde-reductie is. Veel natuurkundige processen worden beschreven met partiële differentiaalvergelijkingen, die een computer oplost door de ruimte op te delen in een heel fijn rooster: soms honderdduizenden tot miljoenen punten. Zo'n volledig model heet het full order model (FOM). Het is nauwkeurig, maar traag.
Bij model-orde-reductie draait men eerst een aantal keren het volledige, trage model en verzamelt daarbij "snapshots": momentopnames van de oplossing op verschillende tijdstippen of onder verschillende omstandigheden. Met een techniek genaamd Proper Orthogonal Decomposition (POD) worden uit die snapshots de belangrijkste terugkerende patronen gedestilleerd, vergelijkbaar met hoe je uit duizenden foto's van gezichten een klein aantal "typische gezichtstrekken" kunt afleiden waarmee je vrijwel elk gezicht kunt benaderen. Met zo'n kleine set patronen (een reduced basis) kan het model daarna in een veel lagere dimensie worden opgelost: in plaats van miljoenen onbekenden nog maar tientallen.
Voor lineaire systemen werkt dat uitstekend. Het probleem ontstaat bij niet-lineaire termen. Ook al zit de oplossing zelf in een kleine, gereduceerde ruimte, om de niet-lineaire functie te evalueren moet de computer eerst de volledige, hoge-dimensionale oplossing terugreconstrueren en de functie op elk van de miljoenen originele punten opnieuw berekenen. Dit staat bekend als de "lifting bottleneck": de reductie van de lineaire delen levert dan nauwelijks snelheidswinst op, omdat het niet-lineaire deel alsnog het volledige rekenwerk vergt.
Hier komt DEIM in beeld. De methode, voorgesteld door Saifon Chaturantabut en Danny C. Sorensen in 2010, bouwt een aparte, kleine basis specifiek voor de niet-lineaire term, op dezelfde manier als POD dat doet voor de oplossing zelf. Vervolgens kiest een gulzig ("greedy") algoritme stap voor stap een klein aantal specifieke roosterpunten — de interpolatie-indices — waarop de niet-lineaire functie daadwerkelijk wordt uitgerekend. Elk nieuw punt wordt gekozen op de plek waar de huidige benadering nog de grootste fout vertoont, zodat elk extra punt maximale extra informatie oplevert. Met die handvol functiewaarden en een vooraf berekende matrix wordt de volledige niet-lineaire vector daarna wiskundig gereconstrueerd, zonder de functie overal te hoeven evalueren. Het rekenwerk schaalt zo mee met het aantal gekozen punten in plaats van met het aantal roosterpunten van het oorspronkelijke model.
DEIM zelf bouwt voort op een oudere, verwante techniek: de Empirical Interpolation Method (EIM), geïntroduceerd in 2004 door Maxime Barrault, Yvon Maday, Ngoc Cuong Nguyen en Anthony Patera voor het benaderen van functies die van een parameter afhangen. DEIM past dat idee toe op de discrete, algebraïsche vergelijkingen die uit een computerrooster ontstaan — vandaar het woord "discreet" in de naam. Een latere, numeriek stabielere variant, Q-DEIM, gebruikt QR-decompositie met kolompivotering (een standaardtechniek uit de lineaire algebra) om de interpolatiepunten te kiezen, en is rond 2016 uitgewerkt door Zlatko Drmač en Serkan Gugercin.
Wat wil men ermee bereiken?
Het uiteindelijke doel is simulaties te versnellen zonder al te veel nauwkeurigheid te verliezen, juist in situaties waarin een model heel vaak opnieuw moet worden doorgerekend. Denk aan het optimaliseren van de vorm van een vliegtuigvleugel: daarvoor moet dezelfde luchtstromingssimulatie honderden keren draaien met kleine ontwerpvariaties. Of aan regeltechniek, waarbij een besturingssysteem in milliseconden moet kunnen voorspellen hoe een systeem zich gedraagt. Ook bij onzekerheidsanalyse — waarbij een model duizenden keren met licht andere invoerwaarden wordt doorgerekend om een betrouwbaarheidsmarge te bepalen — is snelheid cruciaal.
Een breder motief is de opkomst van digital twins: digitale, voortdurend bijgewerkte kopieën van fysieke systemen zoals bruggen, windturbines of productielijnen, die in (bijna) realtime moeten meedraaien met de werkelijkheid. Een volwaardige, niet-gereduceerde simulatie is daarvoor vaak te traag; DEIM en verwante technieken proberen die kloof te overbruggen zodat gedetailleerde fysische modellen toch bruikbaar worden voor snelle beslissingen.
Voorbeelden uit de praktijk
In het oorspronkelijke artikel uit 2010 demonstreerden Chaturantabut en Sorensen hun methode onder meer op het FitzHugh-Nagumo-model, een vereenvoudigd wiskundig model van hoe een zenuwcel een elektrisch signaal (een actiepotentiaal) doorgeeft. Dit relatief eenvoudige, sterk niet-lineaire testmodel is sindsdien een veelgebruikte benchmark geworden voor nieuwe varianten van DEIM.
Chaturantabut paste de methode in haar promotieonderzoek aan Rice University (rond 2011) ook toe op simulaties van mengbare stroming in poreuze media, zoals het verspreiden van vloeistoffen in ondergrondse oliereservoirs — een rekenintensief probleem waarbij snellere modellen helpen bij reservoirbeheer.
In de jaren daarna is DEIM onderzocht voor chemische kinetiek en verbrandingsmodellen, waarbij reactiesnelheden van tientallen chemische stoffen sterk niet-lineair zijn en normaliter zeer rekenintensief om te simuleren; onderzoekers verbonden aan onder meer Sandia National Laboratories hebben hiermee geëxperimenteerd om reagerende-stromingsmodellen te versnellen.
In de lucht- en ruimtevaart is er onderzoek, onder andere vanuit de groep van Karen Willcox (destijds MIT), naar het gebruik van gereduceerde niet-lineaire aerodynamische modellen voor snellere ontwerpoptimalisatie van vleugels en vliegtuigconfiguraties.
Daarnaast fungeert de MORwiki, een benchmarkverzameling gehost door het Max-Planck-Institut in Magdeburg, als een verzamelplaats van testproblemen — waaronder DEIM-toepassingen — waarmee onderzoekers wereldwijd nieuwe varianten van de methode onderling vergelijken. Het gaat hierbij vooral om academische en onderzoeksmatige demonstraties; grootschalige, publiek gedocumenteerde industriële toepassingen zijn schaarser en vaak niet in detail openbaar gemaakt door bedrijven.
Hoe ver is de techniek?
Binnen de numerieke wiskunde en scientific computing geldt DEIM inmiddels als een gevestigde, goed onderbouwde methode: sinds de introductie in 2010 zijn er honderden vervolgpublicaties verschenen, met varianten als Q-DEIM (2016) voor betere numerieke stabiliteit, tensor-DEIM voor meerdimensionale data, en gelokaliseerde of adaptieve versies die proberen om te gaan met sterk veranderlijke, moeilijk te vangen niet-lineariteiten zoals schokgolven of turbulentie.
De methode is ook terechtgekomen in onderzoeksgerichte software, zoals het open-source Python-pakket pyMOR, mede ontwikkeld aan de Universiteit Münster, en in diverse academische MATLAB-implementaties. Grootschalige, kant-en-klare industriële adoptie is echter nog beperkt: DEIM wordt vooral toegepast binnen onderzoeksafdelingen van lucht- en ruimtevaart- en automotivebedrijven, vaak in samenwerking met universiteiten, en minder als standaardonderdeel van commerciële simulatiesoftware.
Belangrijke obstakels blijven bestaan. DEIM werkt het best wanneer de niet-lineaire term zich met een beperkt aantal patronen laat vangen; bij zeer chaotische of sterk parameterafhankelijke systemen (zoals turbulente stroming) is een veel grotere basis nodig, wat de snelheidswinst vermindert. Ook is er een reëel risico op extrapolatie: als een simulatie een situatie tegenkomt die sterk afwijkt van de eerder verzamelde snapshots, kan de nauwkeurigheid van de benadering onvoorspelbaar terugvallen. Onderzoek naar adaptieve methoden die de basis "on the fly" bijwerken, probeert dit te ondervangen, maar is nog volop in ontwikkeling.
Wie werken eraan?
De methode is bedacht door Saifon Chaturantabut en Danny C. Sorensen, verbonden aan Rice University in de Verenigde Staten. De onderliggende Empirical Interpolation Method komt van Maxime Barrault, Yvon Maday (Sorbonne Université), Ngoc Cuong Nguyen en Anthony Patera (Massachusetts Institute of Technology). De stabielere Q-DEIM-variant is ontwikkeld door Zlatko Drmač (Universiteit van Zagreb, Kroatië) en Serkan Gugercin (Virginia Tech, VS).
Een van de belangrijkste onderzoekscentra voor model-orde-reductie in het algemeen is het Max-Planck-Institut für Dynamik komplexer technischer Systeme in Magdeburg, Duitsland, met onderzoeksleider Peter Benner, dat ook de eerdergenoemde MORwiki-benchmarkverzameling host. In de Verenigde Staten is Karen Willcox (tegenwoordig verbonden aan het Oden Institute van de University of Texas at Austin) een vooraanstaande naam op het gebied van gereduceerde modellen voor lucht- en ruimtevaarttoepassingen, en werkte Kevin Carlberg (voorheen Sandia National Laboratories) aan de verwante GNAT-methode. Aan de Universiteit Münster leidt Mario Ohlberger onder meer de ontwikkeling van het open-source softwarepakket pyMOR. Kortom: dit is voornamelijk een academisch onderzoeksveld, geconcentreerd in de VS en Duitsland, met bijdragen uit onder meer Kroatië en Frankrijk, en met sluimerende maar groeiende interesse vanuit de industrie via toepassingen op digital twins.