SIAM Short Course on Automatic Differentiation
Sunday, May
19, 2002
Westin Harbour Castel Hotel, Toronto, Canada
Organizers
Andreas Griewank,
Technical University Dresden, Germany
Uwe Naumann, University of Hertfordshire, UK
Andrea Walther, Technical University Dresden, Germany
Rationale
The solutions
of nonlinear continuous optimization problems are always characterized by
neccessary conditions involving first and possibly second derivatives of objective
and constraint functions. Moreover, most deterministic optimization algorithms
for nonlinear problems are based on local Taylor expansions defined in terms
of gradients, Jacobians and Hessians. Hence the efficient provision of accurate
derivative information has always been a key concern in practical optimization.
The chainrule based technique of automatic differentiation provides first
and higher derivatives without incurring any truncation errors. The derivative
evaluation cosast can be estimated a priori as a multiple of the cost for
evaluating the undifferentiated function(s).
Software for the automatic differentiation of problem functions specified
by evaluation programs in Fortran or C has become widely available in the
last decade. As an indication of their reliability and convenience we note
that these tools have been routinely employed in the optimization server NEOS
provided by Argonne National Laboratory and Northwestern University. The possibility
to evaluate accurate sensitivities even for very complex computer models facilitates
the application of rapidly convergent optimization methods to modern parameter
estimation and design optimization problems with very many free variables.
As with all computational methodologies, an understanding of the underlying
principles allows the user to select and employ the available software tools
safely and efficiently. For large scale applications an appropriate compromise
between runtime and memory requirement should be sought.
This course will introduce the basics of AD theory and tools as well as developments
dealing with more advanced issues including differentiating iterative and
adaptive codes, evaluating higher oder derivatives, and space-time trade-offs.
Description
The main
objective of this one day short course is to give participants a detailed
overview of AD techniques and tools. In particular, all participants will
be enabled to select appropriate modes and to estimate the cost of evaluating
all first and second derivatives that are required in various optimization
scenarios.
Examples of real-world applications will be used to illustrate the importance
of exact derivative information as part of a motivation to start off the day.
The principles behind the two basic modes of AD, i.e. the forward and reverse
modes, are introduced both from a theoretical and a more implementation-oriented
point of view.
The second part of the morning will a practical introduction to AD in the
context of source transformation tools illustrated with the aid of ADIFOR,
ADIC, and Odyssee. Several important issues specific to source transformation
will be discussed. Using some simple examples we show how exact derivative
information can be generated efficiently from an existing Fortran or C Code
using AD.
After lunch we will turn to the implementation of AD using operator overloading.
The basic ideas of this approach are explained. Then, for the same examples
as in the morning the automatic differentiation of C- and MATLAB-codes is
illustrated by applying ADOL-C and ADMAT/ADMIT. The AD packages used in the
two practical sessions were selected as a reasonably representetive sample
of the available AD tools.
In a second part of the afternoon we will discuss several possibilities for
user assistance to enhance the automatic differentiation of source codes.
For example, the detection and exploitation of sparsity and other structure
in nonlinear problems has not yet been fully automated. By employing generalizations
of the column-grouping techniques familiar from differencing one may evaluate
Jacobians with typical sparsity patterns at a small multiple of the cost of
evaluating the underlying vector function.
Furthermore, loops representing iterations or evolutions over a large number
of (pseudo-)time steps can be differentiated much more efficiently than in
a black-box fashion. Finally, methods for computing derivatives of arbitrary
order in one or more variables are explained.
We conclude the afternoon with an outlook on future projects in AD software
development and on open research questions. The integration of AD functionality
into an existing compiler environment is elaborated in some detail. A first
approach and preliminary results are presented.
Instructors
- Andreas Griewank has been a leading researcher and software designer in the area of automatic differentiation for more than a decade. He co-edited the proceedings of three international workshops on AD and authored the book "Evaluating Derivatives, Principles and Techniques of Algorithmic Differentiation" that was published by SIAM in 2000. Andreas is a former senior scientist of Argonne National Laboratory and currently the director of the Institute of Scientific Computing at the Technical University of Dresden.
- Uwe Naumann is a Senior Lecturer in Computer Science at University of Hertfordshire, UK. He has published several articles in the field of AD and he is one of the editors of the proceeding of the last international AD workshop held in Nice, France, in July 2000. His main research interests are the integration of AD into compilers and the exploitation of structure and sparsity of derivatives through elimination techniques in computational graphs.
- Andrea Walther obtained her PhD in mathematics in 1999. The thesis dealt with memory requirement reduction for the reverse mode of AD by applying checkpointing strategies. Over the last couple of years, she has published ten articles. Andrea Walther's current research interests includes the calculation of adjoints using AD and the further development of checkpointing techniques for program reversal on serial and parallel machines.
Who Should Attend?
- Scientists, engineers, and students working in the field of optimization, scientific computing, and applied mathematics.
Recommended Background
Level of Material
Introductory 50%
Intermediate 30%
Advanced 20%
Program
Morning
8:00 - 8:45 Introduction and Motivation
8.45 - 10.00 Basics of Automatic Differentiation
10.00 - 10.30 Coffee break
10.30 - 12.00 Automatic Differentiation by Source Transformation: ADIFOR, ADIC, and Odyssee
Afternoon
12.00 - 1:15 Lunch
1:15 - 2:45 Automatic Differentiation by Operator Overloading: ADOL-C and ADMAT/ADMIT
2:45 - 3:15 Coffee break
3:15 - 4:15 Enhancing efficiency through user assistance
4:15 - 4:45 Compiler integration and other developments
Adjourn
Background Reading