Griebel / Roose / Schlick Advances in Automatic Differentiation

1. Auflage 2008
ISBN: 978-3-540-68942-3
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 368 Seiten

The Fifth International Conference on Automatic Differentiation held from August 11 to 15, 2008 in Bonn, Germany, is the most recent one in a series that began in Breckenridge, USA, in 1991 and continued in Santa Fe, USA, in 1996, Nice, France, in 2000 and Chicago, USA, in 2004. The 31 papers included in these proceedings re?ect the state of the art in automatic differentiation (AD) with respect to theory, applications, and tool development. Overall, 53 authors from institutions in 9 countries contributed, demonstrating the worldwide acceptance of AD technology in computational science. Recently it was shown that the problem underlying AD is indeed NP-hard, f- mally proving the inherently challenging nature of this technology. So, most likely, no deterministic 'silver bullet' polynomial algorithm can be devised that delivers optimum performance for general codes. In this context, the exploitation of doma- speci?c structural information is a driving issue in advancing practical AD tool and algorithm development. This trend is prominently re?ected in many of the pub- cations in this volume, not only in a better understanding of the interplay of AD and certain mathematical paradigms, but in particular in the use of hierarchical AD approaches that judiciously employ general AD techniques in application-speci?c - gorithmic harnesses. In this context, the understanding of structures such as sparsity of derivatives, or generalizations of this concept like scarcity, plays a critical role, in particular for higher derivative computations.

Autoren/Hrsg.

Griebel, Michael

Roose, Dirk

Schlick, Tamar

Chr,

Hovland, Paul

Naumann, Uwe

Utke, Jean

Inhaltsverzeichnis

1;Preface;5
2;Contents;8
3;List of Contributors;11
4;Reverse Automatic Differentiation of Linear Multistep Methods;17
4.1;1 Introduction;17
4.2;2 Linear Multistep Methods;19
4.3;3 Zero-Stability of the Discrete Adjoints;23
4.4;4 Derivatives at the Initial Time;24
4.5;5 Numerical Experiments;26
4.6;6 Conclusions;27
4.7;References;27
5;Call Tree Reversal is NP-Complete;29
5.1;1 Background;29
5.2;2 Data-Flow Reversal is NP-Complete;32
5.3;3 Call Tree Reversal is NP-Complete;34
5.4;4 Conclusion;36
5.5;References;36
5.6;A Reference Code for Result Checkpointing;38
6;On Formal Certification of AD Transformations;39
6.1;1 Introduction;39
6.2;2 Background and Problem Statement;40
6.3;3 Unifying PCC and AD Validation;42
6.4;4 Foundational Certification of AD Transformations;44
6.5;5 Related Work;47
6.6;6 Conclusions and Future Work;47
6.7;References;48
7;Collected Matrix Derivative Results for Forward and Reverse Mode Algorithmic Differentiation;50
7.1;1 Introduction;50
7.2;2 Matrix Product, Inverse and Determinant;51
7.3;3 MLE and the Dwyer/Macphail Paper;56
7.4;4 Validation;57
7.5;5 Conclusions;58
7.6;References;58
8;A Modification of WeeksÌ Method for Numerical Inversion of the Laplace Transform in the Real Case Based on Automatic Differentiation;60
8.1;1 Introduction;60
8.2;2 Preliminaries;62
8.3;3 Remarks on Automatic Differentiation;63
8.4;4 Numerical Experiments;65
8.5;5 Conclusions;69
8.6;References;69
9;A Low Rank Approach to Automatic Differentiation;70
9.1;1 Introduction;70
9.2;2 Methodology;72
9.3;3 Case Study;76
9.4;4 Conclusions and Future Work;79
9.5;References;80
10;Algorithmic Differentiation of Implicit Functions and Optimal Values;81
10.1;1 Introduction;81
10.2;2 Jacobians of an Implicit Function;83
10.3;3 Differentiating an Optimal Value Function;84
10.4;4 Example;86
10.5;5 Conclusion;89
10.6;6 Appendix;90
10.7;References;91
11;Using Programming Language Theory to Make Automatic Differentiation Sound and Efficient;92
11.1;1 Introduction;92
11.2;2 Functional Programming and Modularity in AD;94
11.3;3 The AD Transforms Are Higher-Order Functions;95
11.4;4 AD and Differential Geometry;97
11.5;5 Migration to Compile Time;98
11.6;6 Some Preliminary Performance Results;99
11.7;7 Discussion and Conclusion;102
11.8;References;103
12;A Polynomial-Time Algorithm for Detecting Directed Axial Symmetry in Hessian Computational Graphs;104
12.1;1 Introduction;104
12.2;2 Mathematical Definitions;105
12.3;3 Symmetry Detection Algorithm;106
12.4;4 Analysis of the Algorithm;111
12.5;5 Results and Discussion;112
12.6;6 Conclusions and Future Work;114
12.7;References;114
13;On the Practical Exploitation of Scarsity;116
13.1;1 Introduction;116
13.2;2 Scarsity;118
13.3;3 Test Examples;124
13.4;4 Conclusions and Outlook;126
13.5;References;126
14;Design and Implementation of a Context-Sensitive, Flow- Sensitive Activity Analysis Algorithm for Automatic Differentiation;128
14.1;1 Introduction;128
14.2;2 Background;130
14.3;3 Algorithm;132
14.4;4 Experiment;134
14.5;5 Related Work;137
14.6;6 Conclusion;137
14.7;References;138
15;Efficient Higher-Order Derivatives of the Hypergeometric Function;139
15.1;1 Introduction;139
15.2;2 Taylor Coefficient Propagation;142
15.3;3 Double Ionization Application;144
15.4;4 Conclusions;148
15.5;References;148
16;The Diamant Approach for an Efficient Automatic Differentiation of the Asymptotic Numerical Method;150
16.1;1 Introduction;150
16.2;2 Asymptotic Numerical Method (ANM);151
16.3;3 Applying AD to the ANM Computations;154
16.4;4 Diamant: An AD Tool Devoted to the ANM;156
16.5;5 Application to a Nonlinear PDE Problem in Structural Mechanics;157
16.6;6 Conclusion;159
16.7;References;160
17;Tangent-on-Tangent vs. Tangent-on-Reverse for Second Differentiation of Constrained Functionals;161
17.1;1 Introduction;161
17.2;2 Tangent-on-Reverse Approach;163
17.3;3 Tangent-on-Tangent Approach;165
17.4;4 Comparing ToR and ToT Approaches;166
17.5;5 The Art of ToR;168
17.6;6 Conclusion;170
17.7;References;170
18;Parallel Reverse Mode Automatic Differentiation for OpenMP Programs with ADOL- C;172
18.1;1 Introduction;172
18.2;2 The Quantum-Plasma Code;173
18.3;3 Parallel Reverse Mode Using ADOL-C;175
18.4;4 Experimental Results;176
18.5;5 Conclusions;179
18.6;References;180
19;Adjoints for Time-Dependent Optimal Control;183
19.1;1 Background;183
19.2;2 Optimal Control;184
19.3;3 Automatic Differentiation;185
19.4;4 Numerical Results, Conclusion and Outlook;188
19.5;References;192
20;Development and First Applications of TAC++;194
20.1;1 Introduction;194
20.2;2 Test Codes;195
20.3;3 TAC++;196
20.4;4 Performance;198
20.5;5 First TAC++ Applications;201
20.6;6 Conclusions;202
20.7;References;203
21;TAPENADE for C;205
21.1;1 Introduction;205
21.2;2 Front-end and Back-end for C;207
21.3;3 Declaration Statements;207
21.4;4 Parameter-Passing Mechanism;210
21.5;5 Alias Analysis;210
21.6;6 Conclusion;213
21.7;References;215
22;Coping with a Variable Number of Arguments when Transforming MATLAB Programs;216
22.1;1 Introduction;216
22.2;2 Passing Arguments in MATLAB;217
22.3;3 Transforming Default Arguments;219
22.4;4 Transforming Argument Lists of Variable Length;222
22.5;5 A More Significant Example;224
22.6;6 Concluding Remarks and Open Questions;225
22.7;References;226
23;Code Optimization Techniques in Source Transformations for Interpreted Languages;228
23.1;1 Introduction;228
23.2;2 Code Optimization Techniques;229
23.3;3 Performance of Code Generated by ADiMat;234
23.4;4 Performance of Code Generated by ADiCape;236
23.5;5 Concluding Remarks;237
23.6;References;237
24;Automatic Sensitivity Analysis of DAE-systems Generated from Equation- Based Modeling Languages;239
24.1;1 Introduction;239
24.2;2 Basic Concepts Behind Simulation Languages;240
24.3;3 Automatic Differentiation of Simulation Languages;243
24.4;4 Overview of ADModelica;246
24.5;5 Summary and FutureWork;248
24.6;References;249
25;Index Determination in DAEs Using the Library indexdet and the ADOL- C Package for Algorithmic Differentiation;251
25.1;1 Introduction;251
25.2;2 Index Determination in DAEs;252
25.3;3 Program for Computing the Index and a Related Library;254
25.4;4 Examples;256
25.5;5 Experiments;258
25.6;6 Conclusions;259
25.7;References;260
26;Automatic Differentiation for GPU-Accelerated 2D/3D Registration;262
26.1;1 Introduction;262
26.2;2 Related Work;263
26.3;3 Review of 2D/3D Registration;264
26.4;4 Automatic Differentiation for a hybrid CPU/GPU Setup;267
26.5;5 Results;269
26.6;6 Conclusions and FutureWork;270
26.7;References;271
27;Robust Aircraft Conceptual Design Using Automatic Differentiation in Matlab;273
27.1;1 Introduction;273
27.2;2 Robust Design Optimization;274
27.3;3 Automatic Differentiation of the Conceptual Design Package;276
27.4;4 Aircraft Sizing Test Case;279
27.5;5 Conclusions;281
27.6;References;281
28;Toward Modular Multigrid Design Optimisation;283
28.1;1 Introduction;283
28.2;2 Simultaneous Timestepping;285
28.3;3 Smoothing Algorithm;287
28.4;4 Multi-level Formulation for the Design;289
28.5;5 Results;290
28.6;6 Conclusions;292
28.7;References;292
29;Large Electrical Power Systems Optimization Using Automatic Differentiation;294
29.1;1 Introduction;294
29.2;2 Optimal Power Flow (OPF) Problem;295
29.3;3 Numerical Experiments;298
29.4;4 Conclusion;302
29.5;References;303
30;On the Application of Automatic Differentiation to the Likelihood Function for Dynamic General Equilibrium Models;304
30.1;1 Introduction;304
30.2;2 General Model Description and Estimation Strategy;305
30.3;3 Implementing AD Derivatives;306
30.4;4 Example Application;307
30.5;5 Monte Carlo Results;310
30.6;6 Conclusion;313
30.7;References;314
31;Combinatorial Computation with Automatic Differentiation;315
31.1;1 Introduction;315
31.2;2 Counting Hamiltonian Cycles;317
31.3;3 Implementation Notes;321
31.4;4 Concluding Remarks;323
31.5;References;325
32;Exploiting Sparsity in Jacobian Computation via Coloring and Automatic Differentiation: A Case Study in a Simulated Moving Bed Process;326
32.1;1 Introduction;326
32.2;2 Automatic Differentiation and Sparsity Pattern Detection;328
32.3;3 Compression via Coloring;330
32.4;4 The Simulated Moving Bed Process;331
32.5;5 Experimental Results;333
32.6;6 Conclusion;336
32.7;References;336
33;Structure-Exploiting Automatic Differentiation of Finite Element Discretizations;338
33.1;1 Introduction;338
33.2;2 Full Black Box AD;340
33.3;3 Exploiting the Structure in Time;341
33.4;4 Exploiting the Structure in Space;343
33.5;5 Numerical Example;346
33.6;6 Conclusion;347
33.7;References;348
34;Large-Scale Transient Sensitivity Analysis of a Radiation- Damaged Bipolar Junction Transistor via Automatic Differentiation;349
34.1;1 Introduction;349
34.2;2 Differentiating Element-Based Models;350
34.3;3 Automatic Differentiation with Sacado;351
34.4;4 Transient Sensitivity Analysis with Rythmos;353
34.5;5 Radiation Defect Semiconductor Device Physics;353
34.6;6 Analysis of a Radiation Damaged BJT;356
34.7;7 Concluding Remarks;358
34.8;References;359
35;Editorial Policy;361
36;General Remarks;362
37;Lecture Notesin Computational Scienceand Engineering;363
38;Monographs in Computational Scienceand Engineering;365
39;Texts in Computational Scienceand Engineering;366