Exploitation of structural sparsity in algorithmic differentiation

• Ausnutzung der strukturellen Dünnbesetztheit im algorithmischen Differenzieren

Varnik, Ebadollah; Naumann, Uwe (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2011)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2011

Kurzfassung

Der Hintergrund dieser Arbeit ist, algorithmisches Differenzierung (AD) der in der Praxis sehr rechenintensiven Vektor-Funktionen, angewendet als Computerprogramme. Traditionell implementieren die meisten AD-Werkzeuge den Vorwärts- bzw. Rückwärtsmodus AD zur Berechnung der Jacobi-Matrix an einer bestimmten Stelle der Eingabe, auf eine Art interner Darstellung wie beispielsweise Hauptspeicher oder Festplatte. In der Tat stellt der Speicher den Flaschenhals von AD vor allem im Rückwärtsmodus dar. Der Vorwärtsmodus AD kann sehr billig in Bezug auf Speicher implementiert werden. Man propagiert dafür zur Laufzeit die Richtungsableitungen vorwärts. Im Gegensatz dazu muss der Rückwärtsmodus gewisse Daten speichern, um den Datenfluss umzukehren und somit Rückwärts-Berechnung der Adjongierten zu ermöglichen. Letzteres ist der Gegenstand der Forschung im AD-Umfeld für skalare Funktionen, da eine einzelne Anwendung des Rückwärtsmodus genügt, um den gesamten Gradienten der Zielfunktion zu akkumulieren. Um den Speicherverbrauch zu reduzieren, wurden Checkpointing-Strategien entworfen, z.B. für zeitabhängige Probleme. Allerdings erfordern sie das Wissen des Anwenders sowohl über die Funktion selbst als auch über den Rückwärtsmodus AD. In diesem Zusammenhang wollen wir ein Werkzeug präsentieren, das den Nicht-AD-Experten die Anwendung des Rückwärtsmodus AD bei seinem Problem wesentlich vereinfacht. Darüber hinaus untersuchen wir Methoden, um die Ausnutzung der strukturellen Eigenschaften der Ableitungstensoren wie Jacobi- und Hesse-Matrizen zu verbessern. Bestehende Methoden basieren auf der Kenntnis der Nichtnull-Muster der Ableitungsstrukturen, in denen eine Kompression in der Regel durch die Anwendung entsprechener Färbungsalgorithmen auf einer grafischen Darstellung erreicht wird. Wir betrachten Distanz-2-Färbung des bipartiten Graphen bzw. Star/Acyclic Färbung der Adjazenzgraphen der Jacobi- bzw. Hesse-Matrix. Wir nutzen die ColPack-Implementierungen dieser Algorithmen. Um eine bessere Kompression zu erzielen, unterscheiden wir zwischen variablen und konstanten Nichnullen, wobei letztere an allen Stellen unverändert bleiben, an denen der Kontrollfluss des darunter liegenden Programms unverändert bleibt. Daher muss nur der variable Teil des jeweiligen Musters zur Laufzeit berechnet werden. Wir stellen allgemeine Laufzeit-Algorithmen zur Verfügung, um die Variablen und Konstanten zu berechnen; wir testen ihre Leistung im Sinne der Laufzeit und erzielter Farben im Prozess der dünnbesetzten Jacobi- und Hesse-Akkumulation. Darüberhinaus präsentieren wir einen Algorithmus, welches das Dünnbesetztheitsmuster der Hesse-Matrix, das wir als das konservative Muster bezeichnen, überschätzt. Das ist das Resultat der Ausnutzung der parziellen Separabellität der zugrunde liegenden Funktion. Wir präsentieren numerische Resultate im Sinne der Laufzeit und der erzielten Farben und vergleichen diese mit denen des genauen Nichtnull-Musters. Die Laufzeitkomplexität der letzteren ist quadratisch. Schließlich erweitern wir den konservativen Algorithmus zu einer rekursiven Version, die wir als das rekursive Muster der Hesse bezeichnen. Der rekursive Algorithmus soll die Richtung des Genauen konvergieren für ausreichend große Rekursionstiefe. Dabei ergibt sich für die Rekursionstiefe eins genau das gleiche Muster wie das konservative.