The Numerical Algorithms Group (NAG), Argonne National Laboratory and the National Physical Laboratory have announced the awarding of the 2015 Wilkinson Prize to P.E. Farrell of the University of Oxford, S.W. Funke of the Simula Research Laboratory, D.A. Ham of Imperial College London and M.E. Rognes of the Simula Research Laboratory for “dolfin-adjoint,” a package which automatically derives and solves adjoint and tangent linear equations from high-level mathematical specifications of finite element discretizations of partial differential equations.
The Wilkinson Prize was established to honor the outstanding contributions of Dr. James Hardy Wilkinson to the field of numerical software. It is awarded every four years to the entry that best addresses all phases of the preparation of numerical software at the International Congress on Industrial and Applied Mathematics by Argonne National Laboratory, the National Physical Laboratory and the Numerical Algorithms Group. The recipients are authors of an outstanding piece of numerical software, judged on:
- clarity of the software implementation and documentation
- importance of the application(s) addressed by the software
- portability, reliability, efficiency and usability of the software implementation
- clarity and depth of analysis of the algorithms and the software in the submission
- quality of the test software
The 2015 prize will be presented at ICIAM 2015 in Beijing and will consist of $3000 plus a commemorative plaque for each winner. Previous Wilkinson Prize winners include
- 2011: Andreas Waechter and Carl D. Laird for Ipopt.
- 2007: Wolfgang Bangerth for deal.II.
- 2003: Jonathan Shewchuch for Triangle.
- 1999: Matteo Frigo and Steven Johnson for FFTW.
- 1995: Chris Bischof and Alan Carle for ADIFOR.
- 1991: Linda Petzold for DASSL.
As the dolfin-adjoint project details on its Web site, the need for adjoints of partial differential equations (PDEs) pervades science and engineering. Adjoints enable the study of the sensitivity and stability of physical systems, and the optimization of designs subject to constraints. While deriving the adjoint model associated with a linear stationary forward model is straightforward, the derivation and implementation of adjoint models for nonlinear or time-dependent models is notoriously difficult. Dolfin-adjoint solves this problem by automatically analyzing and exploiting the high-level mathematical structure inherent in finite element methods. It is implemented on top of the FEniCS Project for finite element discretizations.
Speaking of the 2015 winning software, Mike Dewar, Chair of the Wilkinson Prize Board of Trustees and Chief Technical Officer at NAG said “dolfin-adjoint is an excellent piece of software that can solve problems in a range of application areas. Through its elegant use of high-level abstractions it makes performing what is usually a very challenging piece of computation seem extremely natural.”
The dolfin-adjoint project automatically derives the discrete adjoint and tangent linear models from a forward model written in the Python interface to DOLFIN. These adjoint and tangent linear models are key ingredients in many important algorithms, such as data assimilation, optimal control, sensitivity analysis, design optimization and error estimation. Such models have made an enormous impact in fields such as meteorology and oceanography, but their use in other scientific fields has been hampered by the great practical difficulty of their derivation and implementation.
In his recent book titled The Art of Differentiating Computer Programs: An Introduction to Algorithmic Differentiation (2011), Uwe Naumann states that the “automatic generation of optimal (in terms of robustness and efficiency) adjoint versions of large-scale simulation code is one of the great open challenges in the field of High-Performance Scientific Computing.” The dolfin-adjoint project aims to solve this problem for the case where the model is implemented in the Python interface to DOLFIN.
- It works for both steady and time-dependent problems and for both linear and nonlinear problems.
- Using it is very easy: given a differentiable forward model, employing dolfin-adjoint involves changing on the order of 10 lines of code.
- The adjoint and tangent linear models exhibit optimal theoretical efficiency. If every forward variable is stored, the adjoint takes 0.2-1.0x the runtime of the forward model, depending on the precise details of the structure of the forward problem.
- If the forward model runs in parallel, the adjoint and tangent linear models also run in parallel with no modification.
- If instructed, the adjoint model can automatically employ optimal checkpointing schemes to mitigate storage requirements for long nonlinear runs.
- Rigorous verification routines are provided, so that users can easily verify for themselves the correctness of the derived models.
- It solves optimization problems constrained by partial differential equations by interfacing to powerful optimization algorithms
To do all this, dolfin-adjoint requires cooperation from the model developer:
- It works only with the Python interface of DOLFIN.
- For the adjoint to be consistent, the discretization must be differentiable.
- All changes to object values (matrices, vectors, functions) must happen through the DOLFIN interface.
How it works
The project site explains that the traditional approach to deriving adjoint and tangent linear models is called algorithmic differentiation (also called automatic differentiation). The fundamental idea of algorithmic differentiation is to treat the model as a sequence of elementary instructions. An elementary instruction is a simple operation such as addition, multiplication or exponentiation. Each one of these operations is differentiated individually, and the derivative of the whole model is then composed with the chain rule.
However, the dolfin-adjoint project is based on a very different approach. The model is considered as a sequence of equation solves. This abstraction is similar to the fundamental abstraction of algorithmic differentiation, but operates at a much higher level of abstraction. This idea is implemented in a software library, libadjoint. When this new idea is combined with the high-level abstraction of the FEniCS system, many of the difficult problems associated with algorithmic differentiation dissolve.
The dolfin-adjoint project is developed and maintained by the following authors:
- Patrick E. Farrell, Mathematical Institute, University of Oxford
- Simon W. Funke, Center for Biomedical Computing, Simula Research Laboratory / Applied Modelling and Computation Group, Imperial College London
- David A. Ham, Department of Mathematics and Department of Computing, Imperial College London
- Marie E. Rognes, Center for Biomedical Computing, Simula Research Laboratory
- James R. Maddison, School of Mathematics, University of Edinburgh
For further information
- Wilkinson Prize: http://www.nag.com/other/WilkinsonPrize.html
- Dolfin-adjoint features: http://dolfin-adjoint-doc.readthedocs.org/en/latest/features/index.html