Efficiënt Algoritmisch Differentiëren met behulp van gerichte acyclische grafen

Abstract

Dankzij de groei binnen de technologie wordt algoritmische differentiatie een steeds groter onderwerp in de informatica. Het levert een nauwkeurige waarde van een willekeurige afgeleide op, terwijl de numerieke berekening ervan slechts een schatting oplevert. Binnen de algoritmische differentiatie zijn er twee bekende methoden: de forward en de reverse method. In dit verslag zullen de twee methoden worden besproken en zal er worden onderzocht of er een snellere methode bestaat. Dit wordt gedaan aan de hand van een voorbeeld van het inverse probleem van de één-dimensionale golfvergelijking. Om dit minimaliseringsprobleem op te kunnen lossen, is namelijk de afgeleide nodig. De waarden van deze afgeleide worden bepaald met behulp van een numerieke berekening en algoritmische differentiatie. Onder dat laatste valt de forward method, de reverse method en een tussenliggende methode, die gebruik maakt van parallelle berekeningen. Vervolgens worden de resultaten van deze methoden met elkaar vergeleken en volgt er een algoritme, die op een willekeurige (niet-)lineaire functie is toe te passen. Met behulp van gerichte acyclische grafen bepaalt dit algoritme welke volgorde van berekeningen resulteert in het snelste programma.