Search

Least-squares problems occur often in practice, for example, when a parametrized model is used to describe a behavior of a chemical, physical or an economic application. In this paper, we describe a method for solving least-squares problems that are given as a large system of equations. The solution combines the commonly used methods with algorithmic differentiation and shared-memory multiprocessing. The system of equations contains model functions that are independent from each other. This independence enables the usage of a multiprocessing approach. With help of algorithmic differentiation by source transformation, we obtain the derivative code of the residual function. The advantage of using source transformation is that we can transform the OpenMP pragmas of the input code into corresponding pendants in the derivative code. This is, in particular in the adjoint case, not a straightforward approach. We show the scaling properties of the derivative code and of the optimization process.

PETSc's [1] robustness, scalability and portability makes it the foundation of various parallel implementations of numerical simulation codes. We formulate a least squares problem using a PETSc implementation as the model function and rely on adjoint mode Algorithmic Differentiation (AD) [2] for the accumulation of the derivative information. Various AD tools exist that apply the adjoint model to a given C/C++ code, while none is able to differentiate MPI [3] enabled code. We solved this by combining dco/c++ and the Adjoint MPI library, leading to a fully discrete adjoint implementation of PETSc. We want to underline that this work differs from accumulating derivative information through AD for PETSc algorithms (see e.g. [4]). We compute derivative information of PETSc itself opening up the possibility of an enclosing optimization problem (as needed, e.g., by [5]).

We present a generic approach to transforming one-sided MPI communication in the context of adjoint code. The adjoint allows us to compute gradients of multivariate function implementations at a computational cost that is independent of the size of these gradients. In this paper, we apply the adjoint model to codes containing one-side MPI communication. The Partitioned Global Address Space notation is used to derive the corresponding adjoint code. Our adjoint solutions rely on certain workarounds due to limited adjoint support in the current MPI standard. To avoid these, we provide a wish list for future MPI standards that potentially lead to a more efficient adjoint communication.

In Mitsos et al. (SIAM Journal on Optimization 20(2):573–601, 2009), a method similar to Algorithmic Differentiation (AD) is presented which allows the propagation of, in general nondifferentiable, McCormick relaxations (McCormick, Mathematical Programming 10(2):147–175, 1976; Steihaug, Twelfth Euro AD Workshop, Berlin, 2011) of factorable functions and of the corresponding subgradients in tangent-linear mode. Subgradients are natural extensions of “usual” derivatives which allow the application of derivative-based methods to possibly nondifferentiable convex and concave functions. The software package libMC (Mitsos et al. SIAM Journal on Optimization 20(2):573–601, 2009) performs the automatic propagation of the relaxation and of corresponding subgradients based on the principles of tangent-linear mode AD by overloading. Similar ideas have been ported to Fortran yielding modMC as part of our ongoing collaboration with the authors of Mitsos et al. (SIAM Journal on Optimization 20(2):573–601, 2009). In this article an adjoint method for the computation of subgradients for McCormick relaxations is presented. A corresponding implementation by overloading in Fortran is provided in the form of amodMC. The calculated subgradients are used in a deterministic global optimization algorithm based on a branch-and-bound method. The superiority of adjoint over tangent-linear mode is illustrated by two examples.

This case study in Algorithmic Differentiation (AD) discusses the semi-automatic generation of an adjoint simulation code in the context of an inverse atmospheric remote sensing problem. In-depth structural and performance analyses allow for the run time factor between the adjoint generated by overloading in C++ and the original forward simulation to be reduced to 3. 5. The dense Jacobian matrix of the underlying problem is computed at the same cost. This is achieved by a hierarchical AD using adjoint mode locally for preaccumulation and by exploiting interface contraction. For the given application this approach yields a speed-up over black-box tangent-linear and adjoint mode of more than 170. Furthermore, the memory consumption is reduced by a factor of 1,000 compared to applying black-box adjoint mode.

A source transformation tool for algorithmic differentiation is introduced, capable of transforming MPI-enabled code into secondorder adjoint code. Our derivative code compiler (dcc) is used for the source transformation while a runtime library handles the adjoining of the MPI routines. This paper describes in detail the link between these two components in order to compute second derivatives. This process is illustrated by a simplified parallel implementation of Burgers' equation in a second-order optimization setting, for example, Newton's method.

We propose a technique for proving correctness of adjoint message passing programs that relies on data dependences in partitioned global address space. As an example we discuss asynchronous unbuffered send/receive using MPI.

A common way to solve PDE constrained optimal control problems by automatic differentiation (AD) is the full black box approach. This technique may fail because of the large memory requirement. In this paper we present two alternative approaches. First, we exploit the structure in time yielding a reduced memory requirement. Second, we additionally exploit the structure in space by providing derivatives on a reference finite element. This approach reduces the memory requirement once again compared to the exploitation in time. We present numerical results for both approaches, where the derivatives are determined by the AD-enabled NAGWare Fortran compiler.

The use of discrete adjoints in the context of a hard time-dependent optimal control problem is considered. Gradients required for the steepest descent method are computed by code that is generated automatically by the differentiation-enabled NAGWare Fortran compiler. Single time steps are taped using an overloading approach. The entire evolution is reversed based on an efficient checkpointing schedule that is computed by revolve. The feasibility of nonlinear optimization based on discrete adjoints is supported by our numerical results.

The data flow of a numerical program is reversed in its adjoint. We discuss the combinatorial optimization problem that aims to find optimal checkpointing schemes at the level of call trees. For a given amount of persistent memory the objective is to store selected arguments and/or results of subroutine calls such that the overall computational effort (the total number of floating-point operations performed by potentially repeated forward evaluations of the program) of the data-flow reversal is minimized. CALL TREE REVERSAL is shown to be NP-complete.

We describe a novel method for the generation of tangent-linear code by augmentation of LL-parsers generated by the software tool ANTLR. The main advantage of this approach to source code augmentation is the missing requirement for an internal representation of the original program. We consider this work as the basis for further investigations into how far this technique can be extended in the context of more sophisticated transformations, for example, the automatic generation of adjoint codes. Our prototype tool AD_C_ANTLR currently accepts a subset of the ANSI C standard. We discuss its theoretical basis, and we present a case study to underline the elegance of the parser-based approach to source augmentation.

We present a new approach to the automatic generation of adjoint codes using automatic differentiation by source transformation. Our method relies on static checkpointing techniques applied to an extended version of the program's call graph. A code template is provided to implement a control structure governing the execution of the adjoint and augmented forward versions of each subroutine in the program. These code variants are generated automatically by algorithms that are independent of the programming language of the original code. The major advantage of this new approach is its flexibility with respect to various reversal schemes.

We report on new results in logarithmic simulated annealing applied to the optimal Jacobian accumulation problem. This is a continuation of work that was presented at the SAGA’01 conference in Berlin, Germany [16]. We discuss the optimal edge elimination problem in linearized computational graphs [15] in the context of linear algebra. We introduce row and column pivoting on the extended Jacobian as analogs to front and back edge elimination in linearized computational graphs. Neighborhood relations for simulated annealing are defined on a metagraph that is derived from the computational graph. All prerequisites for logarithmic simulated annealing are fulfilled for dyadic pivoting, which is equivalent to vertex elimination in linearized computational graphs [7]. For row and column pivoting we cannot yet give a proof that the corresponding elimination sequences are polynomial in size. In practice, however, the likelihood for an exponential elimination sequence to occur is negligible. Numerical results are presented for algorithms based on both homogeneous and inhomogeneous Markov chains for all pivoting techniques. The superiority of row and column pivoting over dyadic pivoting can be observed when applying these techniques to Roe’s numerical flux [17].

We consider the problem of accumulating the Jacobian matrix of a nonlinear vector function by using a minimal number of arithmetic operations. Two new Markowitz-type heuristics are proposed for vertex elimination in linearized computational graphs, and their superiority over existing approaches is shown by several tests. Similar ideas are applied to derive new heuristics for edge elimination techniques. The well known superiority of edge over vertex elimination can be observed only partially for the heuristics discussed in this paper. Nevertheless, significant improvements can be achieved by the new heuristics both in terms of the quality of the results and their robustness with respect to different tiebreaking criteria.

We consider the solution of a (generalized) eigenvalue problem arising in physical oceanography that involves the evaluation of both the tangent-linear and adjoint versions of the underlying numerical model. Two different approaches are discussed. First, tangent-linear and adjoint models are generated by the software tool TAF and used separately. Second, the two models are combined into a single derivative model based on optimally preaccumulated local gradients of all scalar assignments. The coupled tangent-linear / adjoint model promises to be a good solution for small or medium sized problems. However, the simplicity of the example code at hand prevents us from observing considerable run time differences between the two approaches.

The fast computation of gradients in reverse mode Automatic Differentiation (AD) requires the generation of adjoint versions of every statement in the original code. Due to the resulting reversal of the control flow certain intermediate values have to be made available in reverse order to compute the local partial derivatives. This can be achieved by storing these values or by recomputing them when they become required. In any case one is interested in minimizing the size of this set. Following an extensive introduction of the "To-Be-Recorded" (TBR) problem we will present flow equations for propagating the TBR status of variables in the context of reverse mode AD of structured programs.

We present new ideas on how to make simulated annealing applicable to the combinatorial optimization problem of accumulating a Jacobian matrix of a given vector function using the minimal number of arithmetic operations. Building on vertex elimination in computational graphs we describe how simulated annealing can be used to find good approximations to the solution of this problem at a reasonable cost.