Advances in Automatic Differentiation (eBook)

Christian H. Bischof, H. Martin Bücker, Paul Hovland, Uwe Naumann, Jean Utke (Herausgeber)

eBook Download: PDF

2008 | 2008
XVIII, 368 Seiten
Springer Berlin (Verlag)
978-3-540-68942-3 (ISBN)

Infos

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.

Inhalt

Preface 5
Contents 8
List of Contributors 11
Reverse Automatic Differentiation of Linear Multistep Methods 17
1 Introduction 17
2 Linear Multistep Methods 19
3 Zero-Stability of the Discrete Adjoints 23
4 Derivatives at the Initial Time 24
5 Numerical Experiments 26
6 Conclusions 27
References 27
Call Tree Reversal is NP-Complete 29
1 Background 29
2 Data-Flow Reversal is NP-Complete 32
3 Call Tree Reversal is NP-Complete 34
4 Conclusion 36
References 36
A Reference Code for Result Checkpointing 38
On Formal Certification of AD Transformations 39
1 Introduction 39
2 Background and Problem Statement 40
3 Unifying PCC and AD Validation 42
4 Foundational Certification of AD Transformations 44
5 Related Work 47
6 Conclusions and Future Work 47
References 48
Collected Matrix Derivative Results for Forward and Reverse Mode Algorithmic Differentiation 50
1 Introduction 50
2 Matrix Product, Inverse and Determinant 51
3 MLE and the Dwyer/Macphail Paper 56
4 Validation 57
5 Conclusions 58
References 58
A Modification of WeeksÌ Method for Numerical Inversion of the Laplace Transform in the Real Case Based on Automatic Differentiation 60
1 Introduction 60
2 Preliminaries 62
3 Remarks on Automatic Differentiation 63
4 Numerical Experiments 65
5 Conclusions 69
References 69
A Low Rank Approach to Automatic Differentiation 70
1 Introduction 70
2 Methodology 72
3 Case Study 76
4 Conclusions and Future Work 79
References 80
Algorithmic Differentiation of Implicit Functions and Optimal Values 81
1 Introduction 81
2 Jacobians of an Implicit Function 83
3 Differentiating an Optimal Value Function 84
4 Example 86
5 Conclusion 89
6 Appendix 90
References 91
Using Programming Language Theory to Make Automatic Differentiation Sound and Efficient 92
1 Introduction 92
2 Functional Programming and Modularity in AD 94
3 The AD Transforms Are Higher-Order Functions 95
4 AD and Differential Geometry 97
5 Migration to Compile Time 98
6 Some Preliminary Performance Results 99
7 Discussion and Conclusion 102
References 103
A Polynomial-Time Algorithm for Detecting Directed Axial Symmetry in Hessian Computational Graphs 104
1 Introduction 104
2 Mathematical Definitions 105
3 Symmetry Detection Algorithm 106
4 Analysis of the Algorithm 111
5 Results and Discussion 112
6 Conclusions and Future Work 114
References 114
On the Practical Exploitation of Scarsity 116
1 Introduction 116
2 Scarsity 118
3 Test Examples 124
4 Conclusions and Outlook 126
References 126
Design and Implementation of a Context-Sensitive, Flow- Sensitive Activity Analysis Algorithm for Automatic Differentiation 128
1 Introduction 128
2 Background 130
3 Algorithm 132
4 Experiment 134
5 Related Work 137
6 Conclusion 137
References 138
Efficient Higher-Order Derivatives of the Hypergeometric Function 139
1 Introduction 139
2 Taylor Coefficient Propagation 142
3 Double Ionization Application 144
4 Conclusions 148
References 148
The Diamant Approach for an Efficient Automatic Differentiation of the Asymptotic Numerical Method 150
1 Introduction 150
2 Asymptotic Numerical Method (ANM) 151
3 Applying AD to the ANM Computations 154
4 Diamant: An AD Tool Devoted to the ANM 156
5 Application to a Nonlinear PDE Problem in Structural Mechanics 157
6 Conclusion 159
References 160
Tangent-on-Tangent vs. Tangent-on-Reverse for Second Differentiation of Constrained Functionals 161
1 Introduction 161
2 Tangent-on-Reverse Approach 163
3 Tangent-on-Tangent Approach 165
4 Comparing ToR and ToT Approaches 166
5 The Art of ToR 168
6 Conclusion 170
References 170
Parallel Reverse Mode Automatic Differentiation for OpenMP Programs with ADOL- C 172
1 Introduction 172
2 The Quantum-Plasma Code 173
3 Parallel Reverse Mode Using ADOL-C 175
4 Experimental Results 176
5 Conclusions 179
References 180
Adjoints for Time-Dependent Optimal Control 183
1 Background 183
2 Optimal Control 184
3 Automatic Differentiation 185
4 Numerical Results, Conclusion and Outlook 188
References 192
Development and First Applications of TAC++ 194
1 Introduction 194
2 Test Codes 195
3 TAC++ 196
4 Performance 198
5 First TAC++ Applications 201
6 Conclusions 202
References 203
TAPENADE for C 205
1 Introduction 205
2 Front-end and Back-end for C 207
3 Declaration Statements 207
4 Parameter-Passing Mechanism 210
5 Alias Analysis 210
6 Conclusion 213
References 215
Coping with a Variable Number of Arguments when Transforming MATLAB Programs 216
1 Introduction 216
2 Passing Arguments in MATLAB 217
3 Transforming Default Arguments 219
4 Transforming Argument Lists of Variable Length 222
5 A More Significant Example 224
6 Concluding Remarks and Open Questions 225
References 226
Code Optimization Techniques in Source Transformations for Interpreted Languages 228
1 Introduction 228
2 Code Optimization Techniques 229
3 Performance of Code Generated by ADiMat 234
4 Performance of Code Generated by ADiCape 236
5 Concluding Remarks 237
References 237
Automatic Sensitivity Analysis of DAE-systems Generated from Equation- Based Modeling Languages 239
1 Introduction 239
2 Basic Concepts Behind Simulation Languages 240
3 Automatic Differentiation of Simulation Languages 243
4 Overview of ADModelica 246
5 Summary and FutureWork 248
References 249
Index Determination in DAEs Using the Library indexdet and the ADOL- C Package for Algorithmic Differentiation 251
1 Introduction 251
2 Index Determination in DAEs 252
3 Program for Computing the Index and a Related Library 254
4 Examples 256
5 Experiments 258
6 Conclusions 259
References 260
Automatic Differentiation for GPU-Accelerated 2D/3D Registration 262
1 Introduction 262
2 Related Work 263
3 Review of 2D/3D Registration 264
4 Automatic Differentiation for a hybrid CPU/GPU Setup 267
5 Results 269
6 Conclusions and FutureWork 270
References 271
Robust Aircraft Conceptual Design Using Automatic Differentiation in Matlab 273
1 Introduction 273
2 Robust Design Optimization 274
3 Automatic Differentiation of the Conceptual Design Package 276
4 Aircraft Sizing Test Case 279
5 Conclusions 281
References 281
Toward Modular Multigrid Design Optimisation 283
1 Introduction 283
2 Simultaneous Timestepping 285
3 Smoothing Algorithm 287
4 Multi-level Formulation for the Design 289
5 Results 290
6 Conclusions 292
References 292
Large Electrical Power Systems Optimization Using Automatic Differentiation 294
1 Introduction 294
2 Optimal Power Flow (OPF) Problem 295
3 Numerical Experiments 298
4 Conclusion 302
References 303
On the Application of Automatic Differentiation to the Likelihood Function for Dynamic General Equilibrium Models 304
1 Introduction 304
2 General Model Description and Estimation Strategy 305
3 Implementing AD Derivatives 306
4 Example Application 307
5 Monte Carlo Results 310
6 Conclusion 313
References 314
Combinatorial Computation with Automatic Differentiation 315
1 Introduction 315
2 Counting Hamiltonian Cycles 317
3 Implementation Notes 321
4 Concluding Remarks 323
References 325
Exploiting Sparsity in Jacobian Computation via Coloring and Automatic Differentiation: A Case Study in a Simulated Moving Bed Process 326
1 Introduction 326
2 Automatic Differentiation and Sparsity Pattern Detection 328
3 Compression via Coloring 330
4 The Simulated Moving Bed Process 331
5 Experimental Results 333
6 Conclusion 336
References 336
Structure-Exploiting Automatic Differentiation of Finite Element Discretizations 338
1 Introduction 338
2 Full Black Box AD 340
3 Exploiting the Structure in Time 341
4 Exploiting the Structure in Space 343
5 Numerical Example 346
6 Conclusion 347
References 348
Large-Scale Transient Sensitivity Analysis of a Radiation- Damaged Bipolar Junction Transistor via Automatic Differentiation 349
1 Introduction 349
2 Differentiating Element-Based Models 350
3 Automatic Differentiation with Sacado 351
4 Transient Sensitivity Analysis with Rythmos 353
5 Radiation Defect Semiconductor Device Physics 353
6 Analysis of a Radiation Damaged BJT 356
7 Concluding Remarks 358
References 359
Editorial Policy 361
General Remarks 362
Lecture Notesin Computational Scienceand Engineering 363
Monographs in Computational Scienceand Engineering 365
Texts in Computational Scienceand Engineering 366

Produkt-Details

• Erscheint lt. Verlag: 17.8.2008
• Reihe/Serie: Lecture Notes in Computational Science and Engineering
• Reihe/Serie: Lecture Notes in Computational Science and Engineering
• Zusatzinfo: XVIII, 368 p. 111 illus.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Schlagworte: 3D • aes • algorithms • automatic differentiation • Calculus • Computer • Construction • Development • MATLAB • Modeling • OpenMP • Optimization • programming • Programming language • Sensitivity Analysis
• ISBN-10: 3-540-68942-7 / 3540689427
• ISBN-13: 978-3-540-68942-3 / 9783540689423