Search

A set of Fortran subroutines for reverse mode algorithmic (or automatic) differentiation of the basic linear algebra subprograms (BLAS) is presented. This is preceded by a description of the mathematical tools used to obtain the formulae of these derivatives, with emphasis on special matrices supported by the BLAS: triangular, symmetric, and band. All single and double precision BLAS derivatives have been implemented, together with the Cholesky factorization from Linear Algebra Package (LAPACK). The subroutines are written in Fortran 2003 with a Fortran 77 interface to allow use from C and C++, as well as dynamic languages such as R, Python, Matlab, and Octave. The subroutines are all implemented by calling BLAS, thereby attaining fast runtime. Timing results show derivative runtimes that are about twice those of the corresponding BLAS, in line with theory. The emphasis is on reverse mode because it is more important for the main application that we have in mind, numerical optimization. Two examples are presented, one dealing with the least squares modeling of groundwater, and the other dealing with the maximum likelihood estimation of the parameters of a vector autoregressive time series. The article contains comprehensive tables of formulae for the BLAS derivatives as well as for several non-BLAS matrix operations commonly used in optimization.

There are several AD tools available, which all implement different strategies for the reverse mode of AD. The major strategies are primal value taping (implemented e.g. by ADOL-c) and Jacobi taping (implemented e.g. by adept and dco/c++). Especially for Jacobi taping, recent advances by using expression templates make this approach very attractive for large scale software. The current implementations are either closed source or miss essential features and flexibility. Therefore, we present the new AD tool CoDiPack (Code Differentiation Package) in this paper. It is specifically designed for a minimal memory consumption and optimal runtime, such that it can be used for the differentiation of large scale software. An essential part of the design of CoDiPack is the modular layout and the recursive data structures, which do not only allow the efficient implementation of the Jacobi taping approach, but will also enable other approaches like the primal value taping or new research ideas. We will also present the performance value of CoDiPack on a generic PDE example and on the SU2 code., Comment: 21 pages, 11 figures, 6 tables, CoDiPack: https://github.com/SciCompKL/CoDiPack

Adjoint methods have become fundamental ingredients of the scientific computing toolbox over the past decades. Large-scale parameter sensitivity analysis, uncertainty quantification, and nonlinear optimization would otherwise turn out computationally infeasible. The symbolic derivation of adjoint mathematical models for relevant problems in science and engineering and their implementation in consistency with the implementation of the underlying primal model frequently proves highly challenging. Hence, an increased interest in algorithmic adjoints can be observed. The algorithmic derivation of adjoint numerical simulation programs shifts some of the problems faced from functional and numerical analysis to computer science. It becomes a highly complex software engineering task requiring expertise in software analysis, transformation, and optimization. Despite rather mature software tool support for algorithmic differentiation, substantial user intervention is typically required when targeting nontrivial numerical programs. A large number of patterns shared by numerous application codes results in repeated duplication of development effort. The adjoint code design patterns introduced in this article aim to reduce this problem through improved formalization from the software engineering perspective. Fully functional reference implementations are provided through github.

Most numerical ODE solvers require problems to be written as systems of first-order differential equations. This normally requires the user to rewrite higher-order differential equations as coupled first-order systems. Here, we introduce the treeVar class, written in object-oriented Matlab, which is capable of algorithmically reformulating higher-order ODEs to equivalent systems of first-order equations. This allows users to specify problems using a more natural syntax and saves them from having to manually derive the first-order reformulation. The technique works by using operator overloading to build up syntax trees of expressions as mathematical programs are evaluated. It then applies a set of rules to the resulting trees to obtain the first-order reformulation, which is returned as another program. This technique has connections with algorithmic/automatic differentiation. We present how treeVar has been incorporated in Chebfun, greatly improving the ODE capabilities of the system.

A toolbox called ADiGator is described for algorithmically differentiating mathematical functions in MATLAB. ADiGator performs source transformation via operator overloading using forward mode algorithmic differentiation and produces a file that can be evaluated to obtain the derivative of the original function at a numeric value of the input. A convenient by-product of the file generation is the sparsity pattern of the derivative function. Moreover, because both the input and output to the algorithm are source codes, the algorithm may be applied recursively to generate derivatives of any order. A key component of the algorithm is its ability to statically exploit derivative sparsity at the MATLAB operation level to improve runtime performance. The algorithm is applied to four different classes of example problems and is shown to produce runtime efficient derivative code. Due to the static nature of the approach, the algorithm is well suited and intended for use with problems requiring many repeated derivative computations.

This work presents the current design and implementation of ADiJaC, an automatic differentiation tool for Java classfiles. ADiJaC uses source transformation to generate derivative codes in both the forward and the reverse modes of automatic differentiation. We describe the overall architecture of the tool and present various details and examples for each of the two modes of differentiation. We emphasize the enhancements that have been made over previous versions of ADiJaC and illustrate their influence on the generality of the tool and on the performance of the generated derivative codes. The ADiJaC tool has been used to generate derivatives for a variety of problems, including real-world applications. We evaluate the performance of such codes and compare it to derivatives generated by Tapenade, a well-established automatic differentiation tool for Fortran and C/C++. Additionally, we present a more detailed performance analysis of a real-world application. Apart from being the only general-purpose automatic differentiation tool for Java bytecode, we argue that ADiJaC’s features and performance are comparable to those of similar mature tools for other programming languages such as C/C++ or Fortran.

A source transformation via operator overloading method is presented for computing derivatives of mathematical functions defined by MATLAB computer programs. The transformed derivative code that results from the method of this article computes a sparse representation of the derivative of the function defined in the original code. As in all source transformation automatic differentiation techniques, an important feature of the method is that any flow control in the original function code is preserved in the derivative code. Furthermore, the resulting derivative code relies solely upon the native MATLAB library. The method is useful in applications where it is required to repeatedly evaluate the derivative of the original function. The approach is demonstrated on several examples and is found to be highly efficient when compared to well-known MATLAB automatic differentiation programs.

We discuss software tool support for the algorithmic differentiation (AD), also known as automatic differentiation, of numerical simulation programs that contain calls to solvers for parameterized systems of n nonlinear equations. The local computational overhead and the additional memory requirement for the computation of directional derivatives or adjoints of the solution of the nonlinear system with respect to the parameters can quickly become prohibitive for large values of n . Both are reduced drastically by analytical (and symbolic) approaches to differentiation of the underlying numerical methods. Following the discussion of the proposed terminology, we develop the algorithmic formalism building on prior work by other colleagues and present an implementation based on the AD software dco/c++. A representative case study supports the theoretically obtained computational complexity results with practical runtime measurements.

Gradient-based optimization problems are encountered in many fields, but the associated task of differentiating large computer algorithms can be formidable. The operator-overloading approach to performing reverse-mode automatic differentiation is the most convenient for the user but current implementations are typically 10-35 times slower than the original algorithm. In this paper a fast new operator-overloading method is presented that uses the expression template programming technique in C++ to provide a compile-time representation of each mathematical expression as a computational graph that can be efficiently traversed in either direction. Benchmarking with four different numerical algorithms shows this approach to be 2.6--9 times faster than current operator-overloading libraries, and 1.3--7.7 times more efficient in memory usage. It is typically less than 4 times the computational cost of the original algorithm, although poorer performance is found for all libraries in the case of simple loops containing no mathematical functions. An implementation is freely available in the Adept C++ software library.

We present a suite of fast and effective algorithms, encapsulated in a software package called ColPack, for a variety of graph coloring and related problems. Many of the coloring problems model partitioning needs arising in compression-based computation of Jacobian and Hessian matrices using Algorithmic Differentiation. Several of the coloring problems also find important applications in many areas outside derivative computation, including frequency assignment in wireless networks, scheduling, facility location, and concurrency discovery and data movement operations in parallel and distributed computing. The presentation in this article includes a high-level description of the various coloring algorithms within a common design framework, a detailed treatment of the theory and efficient implementation of known as well as new vertex ordering techniques upon which the coloring algorithms rely, a discussion of the package's software design, and an illustration of its usage. The article also includes an extensive experimental study of the major algorithms in the package using real-world as well as synthetically generated graphs.

Tapenade is an Automatic Differentiation (AD) tool which, given a Fortran or C code that computes a function, creates a new code that computes its tangent or adjoint derivatives. Tapenade puts particular emphasis on adjoint differentiation, which computes gradients at a remarkably low cost. This article describes the principles of Tapenade, a subset of the general principles of AD. We motivate and illustrate with examples the AD model of Tapenade, that is, the structure of differentiated codes and the strategies used to make them more efficient. Along with this informal description, we formally specify this model by means of data-flow equations and rules of Operational Semantics, making this the reference specification of the tangent and adjoint modes of Tapenade. One benefit we expect from this formal specification is the capacity to formally study the AD model itself, especially for the adjoint mode and its sophisticated strategies. This article also describes the architectural choices of the implementation of Tapenade. We describe the current performance of Tapenade on a set of codes that include industrial-size applications. We present the extensions of the tool that are planned in a foreseeable future, deriving from our ongoing research on AD.

An object-oriented method is presented that computes without truncation the error derivatives of functions defined by MATLAB computer codes. The method implements forward-mode automatic differentiation via operator overloading in a manner that produces a new MATLAB code that computes the derivatives of the outputs of the original function with respect to the differentiation variables. Because the derivative code has the same input as the original function code, the method can be used recursively to generate derivatives of any order desired. In addition, the approach developed in this article has the feature that the derivatives are generated by simply evaluating the function on an instance of the class, thus making the method straightforward to use while simultaneously enabling differentiation of highly complex functions. A detailed description of the method is presented and the approach is illustrated and shown to be efficient on four examples.

This article introduces the software package TIDES and revisits the use of the Taylor series method for the numerical integration of ODEs. The package TIDES provides an easy-to-use interface for standard double precision integrations, but also for quadruple precision and multiple precision integrations. The motivation for the development of this package is that more and more scientific disciplines need very high precision solution of ODEs, and a standard ODE method is not able to reach these precision levels. The TIDES package combines a preprocessor step in M athematica that generates Fortran or C programs with a library in C. Another capability of TIDES is the direct solution of sensitivities of the solution of ODE systems, which means that we can compute the solution of variational equations up to any order without formulating them explicitly. Different options of the software are discussed, and finally it is compared with other well-known available methods, as well as with different options of TIDES. From the numerical tests, TIDES is competitive, both in speed and accuracy, with standard methods, but it also provides new capabilities.

A new solver for nonlinear boundary-value problems (BVPs) in Matlab is presented, based on the Chebfun software system for representing functions and operators automatically as numerical objects. The solver implements Newton’s method in function space, where instead of the usual Jacobian matrices, the derivatives involved are Fréchet derivatives. A major novelty of this approach is the application of automatic differentiation (AD) techniques to compute the operator-valued Fréchet derivatives in the continuous context. Other novelties include the use of anonymous functions and numbering of each variable to enable a recursive, delayed evaluation of derivatives with forward mode AD . The AD techniques are applied within a new Chebfun class called which allows users to set up and solve nonlinear BVPs, both scalar and systems of coupled equations, in a few lines of code, using the “nonlinear backslash” operator (\). This framework enables one to study the behaviour of Newton’s method in function space.

The computations of the high-order partial derivatives in a given problem are often cumbersome or not accurate. To combat such shortcomings, a new method for calculating exact high-order sensitivities using multicomplex numbers is presented. Inspired by the recent complex step method that is only valid for firstorder sensitivities, the new multicomplex approach is valid to arbitrary order. The mathematical theory behind this approach is revealed, and an efficient procedure for the automatic implementation of the method is described. Several applications are presented to validate and demonstrate the accuracy and efficiency of the algorithm. The results are compared to conventional approaches such as finite differencing, the complex step method, and two separate automatic differentiation tools. The multicomplex method performs favorably in the preliminary comparisons and is therefore expected to be useful for a variety of algorithms that exploit higher order derivatives.

An interactive software environment is proposed that combines numerical simulation codes with optimization software packages in an automated and modular way. It simplifies the experimentation with varying objective functions for common optimization problems such as parameter estimation and optimal experimental design that are frequently encountered in computational science and engineering. The design philosophy takes into consideration the need for derivatives of potentially large-scale simulation codes via automatic differentiation as well as distributed computing in a heterogenous environment via CORBA.

Computationally efficient and accurate derivatives are important to the success of many different types of numerical methods. Automatic differentation (AD) approaches compute truncation-free derivatives and can be efficient in many cases. Although present AD tools can provide a convenient implementation mechanism, the computational efficiency rarely compares to analytically derived versions that have been carefully implemented. The focus of this work is to combine the strength of these methods into a hybrid strategy that attempts to achieve an optimal balance of implementation and computational efficiency by selecting the appropriate components of the target algorithms for AD and analytical derivation. Although several AD approaches can be considered, our focus is on the use of template overloading forward AD tools in C++ applications. We demonstrate this hybrid strategy for a system of partial differential equations in gas dynamics. These methods apply however to other systems of differentiable equations, including DAEs and ODEs.

The source transformation tool for automatic differentiation of Fortran programs ADIFOR uses a preaccumulation technique to speed up tangent-linear codes significantly compared to the standard forward mode. Reverse mode automatic differentiation is applied to all scalar assignments to generate efficient code for the computation of local gradients. It has been well known for some time that reverse mode is not necessarily the optimal choice for the computation of these statement-level gradients as it does not minimize the number of operations required. This article presents an efficient algorithm for the solution of this combinatorial optimization problem. The corresponding software is freely available for downloading on our website. Developers of software for automatic differentiation are invited to integrate the algorithm into their tools. Gradients of scalar multivariate functions can be computed by elimination methods on the linearized computational graph. The combinatorial optimization problem that aims to minimize the number of arithmetic operations performed by the elimination algorithm is known to be NP-complete. In this article we present a polynomial algorithm for solving a relevant subclass of this problem's instances. The proposed method relies on the ability to compute vertex covers in bipartite graphs in polynomial time. A simplified version of this graph algorithm is used in a research prototype of the differentiation-enabled NAGWare Fortran compiler for the preaccumulation of local gradients of scalar assignments in the context of automatic generation of efficient tangent-linear code for numerical programs.

The Open/ADF tool allows the evaluation of derivatives of functions defined by a Fortran program. The derivative evaluation is performed by a Fortran code resulting from the analysis and transformation of the original program that defines the function of interest. Open/ADF has been designed with a particular emphasis on modularity, flexibility, and the use of open source components. While the code transformation follows the basic principles of automatic differentiation, the tool implements new algorithmic approaches at various levels, for example, for basic block preaccumulation and call graph reversal. Unlike most other automatic differentiation tools, Open/ADF uses components provided by the Open/AD framework, which supports a comparatively easy extension of the code transformations in a language-independent fashion. It uses code analysis results implemented in the OpenAnalysis component. The interface to the language-independent transformation engine is an XML-based format, specified through an XML schema. The implemented transformation algorithms allow efficient derivative computations using locally optimized cross-country sequences of vertex, edge, and face elimination steps. Specifically, for the generation of adjoint codes, Open/ADF supports various code reversal schemes with hierarchical checkpointing at the subroutine level. As an example from geophysical fluid dynamics, a nonlinear time-dependent scalable, yet simple, barotropic ocean model is considered. OpenAD/F's reverse mode is applied to compute sensitivities of some of the model's transport properties with respect to gridded fields such as bottom topography as independent (control) variables.

A new approach for computing a sparsity pattern for a Hessian is presented: nonlinearity information is propagated through the function evaluation yielding the nonzero structure. A complexity analysis of the proposed algorithm is given. Once the sparsity pattern is available, coloring algorithms can be applied to compute a seed matrix. To evaluate the product of the Hessian and the seed matrix, a vector version for evaluating second order adjoints is analysed. New drivers of ADOL-C are provided implementing the presented algorithms. Runtime analyses are given for some problems of the CUTE collection.

The availability of first derivatives of vector functions is crucial for the robustness and efficiency of a large number of numerical algorithms. An upcoming new version of the differentiation-enabled NAGWare Fortran 95 compiler is described that uses programming language extensions and a semantic code transformation known as automatic differentiation to provide Jacobians of numerical programs with machine accuracy. We describe a new user interface as well as the relevant algorithmic details. In particular, we focus on the source transformation approach that generates locally optimal gradient code for single assignments by vertex elimination in the linearized computational graph. Extensive tests show the superiority of this method over the current overloading-based approach. The robustness and convenience of the new compiler-feature is illustrated by various case studies.

Automatic differentiation is a technique used to transform a computer code implementing some mathematical function into another program capable of evaluating the function and its derivatives. Compared to numerical differentiation, the derivatives obtained from applying automatic differentiation are free from truncation error, and their computation often requires less time. To increase the efficiency of a black box approach of automatic differentiation, a technique called interface contraction may be used. Interface contraction exploits the local structure of a code to temporarily reduce the global number of derivatives propagated through the code. Two performance models are introduced to predict the potential improvement in the execution time of a program making use of interface contraction compared to a program generated by a black box approach of automatic differentiation. The performance models are validated by numerical experiments carried out on different computing platforms. The computer codes used in the experiments stem from the application areas of neutron scattering and biostatistics.

Combination of object-oriented programming with automatic differentiation techniques facilitates the solution of data fitting, control, and design problems driven by explicit time stepping schemes for initial-boundary value problems. The C++ class fdtd takes a complete specification of a single step , along with some associated code, and assembles from it a complete simulator, along with the linearized and adjoint simulations. The result is a (nonlinear) operator in the sense of the Hilbert Class Library (HCL), a C++ software package for optimization. The HCL operator so produced links directly with any of the HCL optimization algorithms. Moreover the performance of simulators constructed in this way is equivalent to that of optimized Fortran implementations.

The software system PCOMP uses automatic differentiation to calculate derivatives of functions that are defined by the user in a modeling language similar to Fortran. This symbolical representation is converted into an intermediate code, which can be interpreted to calculate function and derivative values at run-time within machine accuracy. Furthermore, it is possible to generate Fortran code for function and gradient evaluation, which has to be compiled and linked separately. The first version of PCOMP was introduced in Dobmann et al. [1995]. In this article, we describe a series of extensions and additional features that have been implemented in the meantime.

ADMIT-1 enables the computation of sparse Jacobian and Hessian matrices, using automatic differentiation technology, from a MATLAB environment. Given a function to be differentiated, ADMIT-1 will exploit sparsity if present to yield sparse derivative matrices (in sparse MATLAB form). A generic automatic differentiation tool, subject to some functionality requirements, can be plugged into ADMIT-1; examples include ADOL-C (C/C++ target functions)and ADMAT (MATLAB target funcitons). ADMIT-1 also allows for the calculation of gradients and has several other related functions. This article provides an introduction to the design and usage of ADMIT-1.

Automatic differentiation is an interesting and important tool for all numerical algorithms that require derivatives, e.g., in nonlinear programming, optimal control, parameter estimation, and differential equations. The basic idea is to avoid not only numerical approximations, which are expensive with respect to CPU time and contain round-off errors, but also hand-coded differentiation. This article introduces the forward and backward accumulation methods and describes the numerical implementation of a computer code with the name PCOMP. The main intention of the approach used is to provide a flexible and portable Fortran code for practical applications. The underlying language is described in terms of a formal grammar and is a subset of Fortran with a few extensions. Besides a parser that generates an intermediate code and that can be executed independently from the evaluation routines, there are other subroutines for the direct computation of function and gradient values, which can be called directly from a user program. On the other hand, it is possible to generate a Fortran code for function and gradient evaluation that can be compiled and linked separately.

An environment for general research into and prototyping of algorithms for reliable constrained and unconstrained global nonlinear optimization and reliable enclosure of all roots of nonlinear systems of equations, with or without inequality constraints, is being developed. This environment should be portable, easy to learn, use, and maintain, and sufficiently fast for some production work. The motivation, design principles, uses, and capabilities for this environment are outlined. The environment includes an interval data type, a symbolic form of automatic differentiation to obtain an internal representation for functions, a special technique to allow conditional branches with operator overloading and interval computations, and generic routines to give interval and noninterval function and derivative information. Some of these generic routines use a special version of the backward mode of automatic differentiation. The package also includes dynamic data structures for exhaustive search algorithms.