F-1 algorithm: Efficient differentiation through large steady-state problems


Benoît Pasquier


Department of Earth System Science of the University of California


Thu, 08/08/2019 - 11:05am


M032, The Red Centre, UNSW


 Steady-state systems of nonlinear partial differential equations (PDEs) are common in engineering and the biogeosciences. These systems are typically controlled by parameters that can be estimated efficiently using second-order optimization algorithms. However, computing the gradient vector and Hessian matrix of a given objective function defined implicitly by the solution of large PDE systems is seldom economical.

A fast and easy-to-use algorithm is introduced for computing the gradient and Hessian of an objective function implicitly constrained by a steady-state PDE system. The algorithm, which is based on the use of hyperdual numbers, is called the F-1 algorithm, because it requires only one factorization of the constraint-equation Jacobian. Careful examination of the relationships that arise from differentiating the PDE system reveal analytical shortcuts that the F-1 algorithm leverages. Benchmarks of the F-1 algorithm against five numerical differentiation schemes are shown in the context of optimizing a global steady-state model of the marine phosphorus cycle that depends explicitly on m=6 parameters. In this context, the F-1 algorithm computes the Hessian 16 to 100 times faster than other algorithms, allowing for the entire optimization procedure to be performed 4 to 26 times faster. This is because other algorithms require O(m) to O(m²) factorizations, which suggests even greater speedups for larger problems.

A live demonstration of using the F-1 algorithm, which is implemented as a Julia package, is given.


Benoît Pasquier is a postdoctoral researcher at the Department of Earth System Science of the University of California, Irvine, working on global marine biogeochemistry models with Prof. J. Keith Moore and Prof. François Primeau. Benoît is an alumnus of UNSW, with a MSc in Environmental Science obtained in 2010 and a PhD in Applied Mathematics obtained in 2017 under the supervision of Prof. Mark Holzer. Prior to returning to academia for his PhD, Benoît has worked as a water-treatment engineer for Suez-Environment and as a FOREX-trader assistant for Société Générale Investment Banking. Benoît also holds a MSc in Engineering from École Polytechnique and a MSc in Finance Mathematics from Paris-Dauphine University and ENSAE ParisTec




School Seminar Series: