Kombinatorische Aspekte der Ableitungsberechnung

• Applicant: Professor Dr. Uwe Naumann
• Subject Area: Computer Architecture, Embedded and Massively Parallel Systems
• Term: from 2008 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 52609407

• Final Report Year: 2012

Final Report Abstract

Ableitungen von Zielgrössen numerischer Simulationen bezüglich diverser Modellparameter spielen eine zentrale Rolle in klassischen und modernen numerischen Methoden. Bei der Algorithmischen Differentiation numerischer Simulationsprogramme werden letztere semantisch so transformiert, dass die resulu tierenden Programme die gewünschten Ableitungen an beliebigen Punkten im Parameterraum berechnen. Es ergeben sich ein Reihe kombinatorischer Probleme, deren Verständnis und (annähernd) optimale Lösung einen enormen Einfluss auf die Effizienz und damit die Anwendbarkeit diverser numerischer Methoden auf gegebene reale Problemstellungen nicht nur in den Natur- oder Ingenieurwissenschaften haben. Ein Untermenge dieser Probleme waren Gegenstand der Forschung und Entwicklung im Rahmen dieses Projekts. Insbesondere ging es um die Weiterentwicklung existierender Eliminationstechniken auf linearisierten (mit lokalen partiellen Ableitungen annotierten) Berechnungsgraphen numerischer Simulationsprogramme. Dafür mussten die zu Beginn des Projekts noch nicht sehr umfangreichen theoretischen Grundlagen zunächst einer eindringlichen Analyse unterzogen werden. Infolgedessen kam es zu einer recht grundlegenden Konkretisierung der Projektziele. Der Fokus wurde von der ursprünglich geplanten Weiterentwicklung heuristischer Lösungsansätze auf deterministische Methoden basierend auf heuristischen Daten verschoben. Im Resultat dieser Richtungskorrektur konnten neue, hochrelevante Einsichten in die Struktur der behandelten Probleme und entsprechende neue Beweistechniken für Optimalitätskriterien entwickelt werden. Der implementierte Algorithmus kann potentiell Anwendung in einer Reihe von Folgeaktivitäten finden.

Publications

• Low-Memory Tour Reversal in Directed Graphs. Dagstuhl Seminar Proceedings 09061, 2009
  V. Mosenkis, U. Naumann, and E. Peise
  
• Branch and bound for optimal Jacobian accumulation. Proceedings of the Fifth SIAM Workshop on Combinatorial Scientific Computing, number AIB-2011-09, Aachener Informatikberichte, pages 73–76. RWTH Aachen, 2011
  V. Mosenkis, E. Peise, and U. Naumann
  
• Combinatorial Problems in Algorithmic Differentiation. Pages 129–162 in: U. Naumann and O. Schenk, eds.: Combinatorial Scientific Computing. Taylor and Francis / CRC Press, 2012
  U. Naumann and A. Walther
  
• On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized dags. Optimization Methods and Software 27:337–358, 2012
  V. Mosenkis and U. Naumann
  (See online at https://doi.org/10.1080/10556788.2011.580745)
• The Art of Differentiating Computer Programs. An Introduction to Algorithmic Differentiation. SIAM, 2012
  U. Naumann