Efficient computation of derivatives for optimal experimental design [Elektronische Ressource] / vorgelegt von Arno Rasch

Sujets

• Informatik
• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2007
• Nombre de lectures: 47
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

E cien t Computation of Derivatives
for Optimal Experimental Design
Von der Fakult at fur Mathematik, Informatik und Naturwissenschaften
der Rheinisch-Westf alischen Technischen Hochschule Aachen
zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften genehmigte Dissertation
vorgelegt von
Diplom-Informatiker
Arno Rasch
aus Aachen
Berichter: Universit atsprofessor Christian H. Bischof, Ph.D.
Universit Dr. Ewald Speckenmeyer
Tag der mundlic hen Prufung: 23. November 2007
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfugbar.Zusammenfassung
Computersimulationen basierend auf mathematischen Modellen zur Beschreibung von phy-
sikalischen Ph anomenen stellen in vielen natur- und ingenieurwissenschaftlichen Disziplinen
ein unverzichtbares Hilfsmittel dar. Dabei ist es oftmals erforderlich, das verwendete Mod-
ell mit Hilfe von experimentell gewonnenen Messdaten zu kalibrieren, d.h. so einzustellen,
dass die Modellvorhersage bestm oglich mit gegebenen Messdaten aus zuvor durchgefuhrten
physikalischen Experimenten ub ereinstimmt. Bei der optimalen Versuchsplanung (optimal
experimental design) wird versucht, diese Experimente so zu gestalten, dass der Informa-
tionsgewinn fur die Kalibrierung des Modells maximiert wird. Dazu werden typischerweise
mathematische Optimierungsverfahren eingesetzt, wobei zur Berechnung der Zielfunktion die
Ableitung des zugrunde liegenden Modells ben otigt wird.
In dieser Arbeit wird gezeigt, wie man die Modellkalibrierung und optimale Versuchs-
planung durch geeignete Software unterstutzen kann. Da diese Prozesse oftmals selbst ex-
perimentellen Charakter haben, d.h. dass Simulationscode, Optimierungsverfahren und Ziel-
funktion h au gen Anderungen unterliegen, wird mit EFCOSS eine neue Umgebung zur au-
tomatisierten Koppelung der verschiedenen Softwarekomponenten vorgestellt. Insbesondere
k onnen diese Komponenten unabh angig voneinander ausgetauscht werden, wodurch dem Be-
nutzer das Experimentieren mit wechselnden Kon gurationen erm oglicht wird. Dabei wird
der fur die Optimierung ben otigte Quellcode zur Berechnung der ersten und zweiten Ableitung
des Computermodells mit Hilfe des automatischen Di erenzierens generiert.
Da der zus atzliche Rechenaufwand und Speicherbedarf fur die Ableitungsberechnung im
Vergleich zur Ausgangsfunktion je nach Problemstellung erheblich steigen kann, werden im
zweiten Teil dieser Dissertation verschiedene Strategien zur E zienzsteigerung, beispielsweise
die automatische Parallelisierung der Ableitungsberechnung mittels OpenMP vorgestellt. Au-
erdem wird die Anwendung des automatischen Di erenzierens auf Quellcode, der bere-
its mit OpenMP parallelisiert ist, sowie eine Kombination verschiedener Parallelisierungs-
strategien untersucht. Bei der Berechnung von zweiten Ableitungen bietet die Ausnutzung der
Dunn besetztheitsstruktur der Hesse-Matrix weiteres Potential zur E zienzsteigerung. Hier-
zu wird ein dynamischer Ansatz vorgestellt, welcher nur solche Matrixelemente berechnet,
die nicht Null sind. Obwohl im Gegensatz zu fruheren statischen Ans atzen keine Annahmen
ub er das Dunn besetztheitsmuster getro en werden, ist der dynamische Ansatz diesen zum
Teil deutlich ub erlegen. Das Ziel einer weiteren Strategie ist die Ausnutzung von Struktur
im Quellcode zur Berechnung von partiell separablen Funktionen. Dabei wird die Technik
der Schnittstellenkontraktion (interface contraction) auf zweite Ableitungen erweitert und
schlie lic h gezeigt, dass durch die Kombination von interface contraction mit einer geeigneten
Parallelisierung gegenub er sogenannten \Black-Box"-Ans atzen des automatischen Di eren-
zierens gerade bei der h au g auftretenden Problemklasse der partiell separablen Funktionen
ein dramatischer E zienzgewinn m oglich ist.Abstract
In many scienti c disciplines, computer simulations based on mathematical models are an
indispensable research tool for studying the phenomenological behavior of physical systems. In
order to use a mathematical model, it is often necessary to adjust some of its parameters such
that the simulation output best matches some given experimental data obtained from physical
experiments|a task often called parameter estimation. In addition, optimal experimental
design methodology, taking into account certain sensitivities of the model, can be used to
maximize the information gained from the physical experiments.
In this thesis, recurring optimization tasks such as parameter estimation and optimal ex-
perimental design are analyzed with a particular focus on software-engineering aspects. A
novel framework for automatically combining simulation- and optimization software is intro-
duced. This framework, called EFCOSS, treats the simulation, the optimization algorithm,
and the mathematical objective function as separated components which can be exchanged
independently in order to facilitate experimenting with frequently changing problem con g-
urations. The rst- and second-order derivatives of the model, which are required to solve
the various optimization problems, are obtained by applying automatic di eren tiation to the
simulation code.
Since compared to the original function evaluation, the derivative calculation is often
signi can tly more expensive in terms of execution time and memory requirement, several
strategies for improving the e ciency of the derivative computation are presented in the sec-
ond part of this thesis. These strategies include, e.g., the automatic parallelization of the
derivative computation with OpenMP. In addition, the application of automatic di eren ti-
ation to OpenMP-parallelized source code is investigated, as well as a combined multilevel-
parallelization strategy. The e ciency of the computation of second-order derivatives can be
further improved by exploiting the sparsity of the Hessian matrix using a dynamic approach,
where only non-zero elements of the Hessian are computed. Although no a priori knowledge
of the sparsity pattern is required, this dynamic approach often outperforms previous static
approaches. Another strategy aims at exploiting the structure of partially separable func-
tions. A general technique called interface contraction is extended to second-order derivative
computation, and its e ciency is demonstrated in the context of partially separable functions.
Finally, a combined approach employing interface contraction and parallelization is presented.
Accompanying performance experiments show a dramatic e ciency increase of this combined
approach, compared to black-box automatic di eren tiation, in particular for the rich class of
partially separable functions.Acknowledgements
This thesis was written during my work as a research scientist at the Institute for Scien-
ti c Computing at RWTH Aachen University. The research was funded by the Deutsche
Forschungsgemeinschaft (DFG) within SFB 401 \Modulation of Flow and Fluid{Structure
Interaction at Airplane Wings".
First I would like to express my gratitude to my advisor, Prof. Christian H. Bischof,
Ph.D., for his support and encouragement he o ered me during my doctoral studies, and
Prof. Dr. Ewald Speckenmeyer from the Institut fur Informatik at University of Cologne for
his interest in my work and his willingness to be the co-referent for my thesis.
Many thanks to my colleague and co-advisor Dr. H. Martin Buc ker for a fruitful collab-
oration, a great working environment, and excellent support at all times. I am also grateful
to my other colleagues at the Institute for Scienti c Computing, namely Oliver Fortmeier,
Michael Lulfesmann, Monika Petera, Andre Vehreschild, and Andreas Wolf, for many valu-
able discussions, productive cooperation and great team spirit. This also includes my former
colleagues, Prof. Dr. Bruno Lang, Jakob W. Risch, and Emil Slusanschi.
Furthermore I would like to thank the members of the High-Performance-Computing group
at the Center for Computing and Communication, Dieter an Mey, Samuel Sarholz, Alexander
Spiegel, and Christian Terboven for enlightening discussions on OpenMP and speci c issues
of the Sun Fire system.
Many thanks to Dr. Paul D. Hovland, Dr. Boyana Norris, and other members of the
Mathematics and Computer Science Division at Argonne National Laboratory, IL, USA, for
their kind hospitality during my research visit in 2002/2003.
I am grateful to Dr. Mike Fagan, for sharing his insight into the ADIFOR 3.0 system,
Ernesto Kriesten for interesting discussions on optimal experimental design and review-
ing Chapter 5, and the various collaborators within SFB 401 for a fruitful and enjoyable
cooperation during the entire research period.i
Contents
1 Introduction 1
2 Optimal Experimental Design and Parameter Estimation 3
2.1 Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Optimal Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Exptal for Parameter Estimation . . . . . . . . . . . . 8
2.4 Software for OED and Parameter Estimation . . . . . . . . . . . . . . . . . . 10
2.4.1 Optimization Software . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4.2 Automatic Di eren tiation . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4.3 The Hessian Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Combining Simulation and Optimization Software 17
4