Programme of the Ninth Euro AD Workshop

In the field of automatic differentiation, graph models are broadly used in the solution of occurring combinatorial problems. Due to the lack of computer-aided visualizing alternatives, even today, a chalkboard is used to analyze graph problems in the AD classes. We present our novel visualization tool for an interactive education of of graph algorithms.

The efficient provision of adjoint information is indispensable for numerous applications in flow control. The complex physical background necessitate a very fine mesh. Thus a corresponding high number of timesteps is required to simulate flows accurately. We want to combine advanced methods of numerical models and methods of mathematical control to improve the flow qualities. For that purpose we modify the common flow simulation software SEMTEX based on a spectral element method. We present a new approach for the exploitation of structure in time and space. For this purpose, recent results for the algorithmic differentiation of finite element discretization and implicit time stepping procedures are combined with appropriate checkpointing strategies.

Adapted to the given structure different techniques for the adjoint calculation are applied to minimize the effort. For flexible parts, like the target function, we use algorithmic differentiation. On the other hand, the timestepping loop of the simulation code is hand adjoint, because this part will remain constant for the considered applications.

Numerical results for a flow control problem and a first optimization illustrate the resulting numerical effort for the computation of the required adjoint information.

Computational biology aims at studying biological problems with the help of computer simulations. I will present some common problems like protein folding and protein docking, where Automatic Differentiation could be of great help for the development of new methods.

An example for an inverse scattering problem is the reconstruction of material properties of a 3D object based on the spatial and temporal analysis of intersecting radar waves. In the context of the CONSERT experiment an orbiter receives scattered emissions from a lander of a comet's surface. For a reconstruction domain of 2km, the permittivity of each of the 700^3 grid elements impacts on the signal at the orbiting receiver. For a given permittivity-field this signal can be computed with the FDTD (finite differences in time domain) method. The corresponding optimization problem is defined by adjusting the permittivity-values to minimize the difference between simulated and received signals. This optimal control problem is solved with a quasi-Newton-algorithm which requires the gradient of the objective function. The gradient is provided by the technique of Algorithmic Differentiation. The numerical complexitiy of this problem and the memory requirements result in a distributed calculation of the objective function and the gradient. We will present numerical results of a parallelization by MPI.

Variational data assimilation consists in estimating control parameters of a numerical model in order to minimize the misfit between the forecast values and some observations. The YAO software implements a new method based on modular graph to handle data assimilation developement matters. YAO disposes of a language allowing a user to specify a numerical model and it generates then the direct and the adjoint C++ code. We present here an automatic parallelization of the generated code. In fact the analysis of the modular graph highlights the dependencies on the computation and consents to avoid the race conditions, allowing an efficient automatic domain decomposition.

Message passing via MPI is widely used in single-program, multiple-data (SPMD) parallel programs. Existing data-flow frameworks do not fully model the semantics of message-passing SPMD programs, which can result in less precise and even incorrect analysis results. We present a context-sensitive data-flow analysis framework based upon the MPI_ICFG for performing interprocedural analysis of message-passing SPMD programs. Our experimental results have shown that using this framework improves the precision of activity analysis and as a result significantly reduces memory requirements for the automatically differentiated versions of a set of parallel benchmarks.

We consider the problem of reversing a tour in a directed graph G=(V,E) with positive integer vertices V and edges E. The tour can be processed in last-in-first-out order as long as the size of the corresponding stack does not exceed the available memory. This constraint is violated in most cases when considering control-flow graphs of large-scale numerical simulation programs. The tour reversal problem also arises in the context of low memory control flow reversal adjoint programs used, for example, in the context of derivative-based nonlinear optimization, sensitivity analysis, or other, often inverse, problems. The intention is to compress the tour in order not to run out of memory. As the general optimal compression problem was proven to be NP-hard and big control-flow graphs result from loops in programs we do not want to use general purpose algorithms to compress the tour. We rather want to compress the tour by finding loops and replace the redundant information by proper representation of the loops. Related work includes methods for run length encoding.

Adjoint derivative models are particularly useful if a function's number of inputs far exceeds the number of outputs. The propagation of adjoints requires the data flow to be reversed, implying the reversal of all communication in programs that use message-passing. We present recent developments in adjoint MPI and its coupling with the overloading mode of the NAG Fortran compiler. A simplified yet representative application problem is discussed as a case study.

Existing programs for AD with the source transformation method are typically based on one specific programing language. GAuDi (GNU Automatic Differentiation) is an AD source transformation tool, which is independent of the programing language. It is based on the gcc, the full GNU Compiler Collection, and transforms the original program source code (Ada, C, C++, Fortran and Java.) into a programming language independent format. GAuDi also innovates the function handling to avoid unnecessary computations. More precisely, it follows the idea that if a differentiated function has different signatures, each signature is assigned a own function. Otherwise it might be possible that a part of the differentiated function is computed even though it not needed. Furthermore it has an open interfaces to easily expand the functionality of this tool. For example the back writing unit of GAuDi can be changed to use the operator overloading approach applied with this source transformation tool.

We review recent developments for overloaded Matlab AD in the MAD package such as: sparse matrix-based AD; method of moments uncertainty estimation.

Tokamaks are the most advanced devices used to control nuclear fusion. In a Tokamak, a hot plasma is confined using magnetic fields in order to achieve the required conditions. The modelling and control of this plasma is a major issue for the development of future fusion devices like ITER.

The coupling between a transport code and an equilibrium code allows simulation of a full plasma discharge. Then, Automatic Differentiation could be a means to solve the problem of control of the plasma position and shape.

We consider a convection-diffusion model in saturated porous media. The aim of this study is to estimate the transport coefficients (diffusion and porosity) from concentration measurements, which is a typical inverse problem. The data consist of the concentration measurements collected in the injection room throughout the experience, as well as the measurements at the final time obtained by core drilling. We use for the direct problem the simulation code TRACES. The inverse problem is formulated as a least square minimization problem in which we minimize the misfit between observations and the corresponding quantities calculated by the model for a given set of parameters. We use TAPENADE for the adjoint derivation of TRACES, and we minimize the cost function with a quasi-Newton algorithm. After estimating the transport parameters, we also consider the identification of the different homogeneous zones in the media.

YAO is a software designed to facilitate the coding of numerical codes and of their adjoints, and so to make easier variationnal assimilation tasks. YAO is based on the decomposition of numerical codes into modular graphs. Each module of the direct code is associated with its Jacobian, which permits an easy construction of the linear tangent and thus of the adjoint of the direct code. A major advantage of YAO is to facilitate the modifications of the code and of its adjoint thanks to the YAO modular graph structure. We have developed the coding of a simplified version of the 3 dimension ocean model NEMO (Gyre configuration) and its adjoint using YAO. We present here validity tests of the computation of the adjoint of the NEMO Gyre configuration.

Despite of the lack of a general framework to search for the optimal combination of Store and Recompute in data-flow reversal, we started development of a data-flow analysis to replace some Storage with cheap Recomputation. This analysis only picks some ``low-hanging fruit'', as it considers only recomputation that obeys some simple data-flow properties. Experiments with Tapenade show measurable improvements for the Push/Pop memory traffic, and thus for run time.