Research

Here are some of the research topics I’ve worked on.

Multiple solutions of nonlinear equations via deflation

Finding multiple solutions of a nonlinear equation, starting from the same guess. (a) Newton's method is started from an initial guess (centre dot) and converges to a solution (blue curve). That solution is then deflated away. (b) Starting from the same initial guess, Newton's method now converges to a different solution (green curve). That solution is also deflated. (c) Starting from the same initial guess, Newton's method finds the final solution (red curve).

Finding multiple solutions of a nonlinear equation, starting from the same guess. (a) Newton’s method is started from an initial guess (centre dot) and converges to a solution (blue curve). That solution is then deflated away. (b) Starting from the same initial guess, Newton’s method now converges to a different solution (green curve). That solution is also deflated. (c) Starting from the same initial guess, Newton’s method finds the final solution (red curve).

Nonlinear equations can permit multiple, distinct solutions. How can we compute such solutions? Answering this question is crucial for the predictive value of computational mathematics: imagine a PDE that permits two solutions, \(A\) and \(B\), and that our computations reveal only the \(A\) solution. All numerical algorithms have converged successfully, and all error measures are satisfied: but if reality chooses the \(B\) solution, then our predictions are worthless. To use numerical simulation as a predictive tool, we must understand and identify the multiple solutions that our models permit.

Another situation where this question arises is in optimisation problems, especially nonlinear nonconvex optimisation problems constrained by partial differential equations. We would like to compute the global minimum of very high-dimensional systems, but scalable search algorithms typically converge to local minima. If we can compute multiple solutions of the associated optimality conditions, then we can identify many local minima, and choose the best one available. This is especially important when some constraints cannot be quantified, such as the aesthetics of the resulting designs.

My research in this area has focussed on deflation techniques for computing multiple solutions of differential equations posed in Banach spaces [1]. Given the differentiable residual of an equation \(\mathcal{F}\) and a solution \(r\), it is possible to construct a new problem \(\mathcal{G}\) with all of the solutions of the original problem, except for the one being deflated. This allows Newton’s method to converge to several different solutions, even starting from the same initial guess.

Crucially, with careful numerical analysis it is possible to design efficient Newton–Krylov preconditioners for the deflated problem from the preconditioner for the original system [1]. If the original problem can be efficiently solved, then the deflated problem can be also: deflation scales to problems with billions of degrees of freedom. Whereas global optimisation algorithms can compute the global minimum for problems of very small dimension, deflation can compute some local minima of arbitrary-dimensional problems [2].

I am currently exploring the many other fascinating applications of deflation: the scalable tracing of bifurcation diagrams, complementarity problems, multimodal Bayesian inference, and computing multiple periodic orbits of dynamical systems.

For this work, I was shortlisted for the 17th IMA Leslie Fox Prize in numerical analysis.

[1] [doi] P. E. Farrell, Á. Birkisson, and S. W. Funke, “Deflation techniques for finding distinct solutions of nonlinear partial differential equations,” SIAM Journal on Scientific Computing, vol. 37, p. A2026–A2045, 2015.
[Bibtex]
@article{farrell2014,
author = {P. E. Farrell and \'A. Birkisson and S. W. Funke},
title = {Deflation techniques for finding distinct solutions of nonlinear partial differential equations},
journal = {{SIAM Journal on Scientific Computing}},
year = {2015},
volume = {37},
issue = {4},
pages = {A2026--A2045},
doi = {10.1137/140984798}
}
[2] P. E. Farrell, Multiple local minima of PDE-constrained optimisation problems via deflation, 2015.
[Bibtex]
@misc{farrell2015a,
note = {arXiv:1508.07633 [math.OC]},
author = {P. E. Farrell},
title = {Multiple local minima of {PDE}-constrained optimisation problems via deflation},
year = {2015},
}

Supermesh construction

(a) and (b): Input meshes. (c) The supermesh of (a) and (b), coloured to show the elements of (a). (d): The same supermesh as (c), coloured to show the elements of (b).

(a) and (b): Input meshes. (c) The supermesh of (a) and (b), coloured to show the elements of (a). (d): The same supermesh as (c), coloured to show the elements of (b).

 

In my PhD thesis I studied algorithms for the construction of the supermesh of two meshes, a problem of computational geometry that arises in many situations of computational mathematics. A supermesh \(\mathcal{S}\) is a mesh of the intersections of the elements of two input meshes \(\mathcal{A}\) and \(\mathcal{B}\). The key property of a supermesh is that it can represent data from both input meshes exactly: when equipped with a finite element, the function space on the supermesh \(\mathcal{V}_{\mathcal{S}}\) is a superspace of the two input function spaces  \(\mathcal{V}_{\mathcal{A}}\) and \(\mathcal{V}_{\mathcal{B}}\).

Supermeshes are used for conservative interpolation between two meshes [1], to compute diagnostics of unstructured mesh simulations [2, 3], for embedding moving meshes via the Arbitrary Mesh Interface method [4], and for coupling models together [5, 6].

In my work, I designed the first algorithms for supermesh construction that were fast enough for practical use [7, 1]. This work won a prize from the UK Association of Computational Mechanics in Engineering; won the departmental PhD prize at Imperial College London; and shared in the Imperial College Research Excellence Award. I represented the UK at the PhD thesis competition of the European Community on Computational Methods in Applied Sciences.

My algorithms were independently implemented in OpenFOAM, the major open-source package for industrial computational fluid dynamics, and I consulted on the application of supermeshing to model coupling for Babcock & Wilcox Nuclear Energy, Inc.

[1] [doi] P. E. Farrell and J. R. Maddison, “Conservative interpolation between volume meshes by local Galerkin projection,” Computer methods in applied mechanics and engineering, vol. 200, iss. 1-4, pp. 89-100, 2011.
[Bibtex]
@article{farrell2009c,
author = {P. E. Farrell and J. R. Maddison},
title = {Conservative interpolation between volume meshes by local {G}alerkin projection},
journal = {Computer Methods in Applied Mechanics and Engineering},
volume = {200},
number = {1-4},
pages = {89--100},
year = {2011},
doi = {10.1016/j.cma.2010.07.015},
}
[2] [doi] P. E. Farrell, “The addition of fields on different meshes,” Journal of computational physics, vol. 230, iss. 9, pp. 3265-3269, 2011.
[Bibtex]
@article{farrell2011a,
author = {P. E. Farrell},
title = {The addition of fields on different meshes},
journal = {Journal of Computational Physics},
volume = {230},
number = {9},
pages = {3265--3269 },
year = {2011},
doi = {10.1016/j.jcp.2011.01.028},
}
[3] [doi] J. R. Maddison and P. E. Farrell, “Directional integration on unstructured meshes via supermesh construction,” Journal of computational physics, vol. 231, iss. 12, pp. 4422-4432, 2012.
[Bibtex]
@article{maddison2012a,
author = {J. R. Maddison and P. E. Farrell},
title = {Directional integration on unstructured meshes via supermesh construction},
journal = {Journal of Computational Physics},
volume = {231},
number = {12},
pages = {4422--4432},
year = {2012},
doi = {10.1016/j.jcp.2012.02.009},
}
[4] [doi] Q. Wang, H. Zhou, and D. Wan, “Numerical simulation of wind turbine blade-tower interaction,” Journal of marine science and application, vol. 11, iss. 3, pp. 321-327, 2012.
[Bibtex]
@article{wang2012,
year={2012},
journal={Journal of Marine Science and Application},
volume={11},
number={3},
doi={10.1007/s11804-012-1139-9},
title={Numerical simulation of wind turbine blade-tower interaction},
author={Wang, Q. and Zhou, H. and Wan, D.},
pages={321--327},
}
[5] [doi] A. Viré, J. Xiang, F. Milthaler, P. E. Farrell, M. D. Piggott, J. -P. Latham, D. Pavlidis, and C. C. Pain, “Modelling of fluid-solid interactions using an adaptive-mesh fluid model coupled with a combined finite-discrete element model,” Ocean dynamics, vol. 62, iss. 10–12, pp. 1487-1501, 2012.
[Bibtex]
@article{vire2012,
author = {A. Vir\'e and J. Xiang and F. Milthaler and P. E. Farrell and M.D. Piggott and J.-P. Latham and D. Pavlidis and C. C. Pain},
journal = {Ocean Dynamics},
pages = {1487--1501},
title = {Modelling of fluid-solid interactions using an adaptive-mesh fluid model coupled with a combined finite-discrete element model},
volume = {62},
number = {10--12},
year = {2012},
doi = {10.1007/s10236-012-0575-z}
}
[6] [doi] A. G. Buchan, P. E. Farrell, G. J. Gorman, A. J. H. Goddard, M. D. Eaton, E. T. Nygaard, P. L. Angelo, R. P. Smedley-Stevenson, S. R. Merton, and P. N. Smith, “The immersed body supermeshing method for modelling reactor physics problems with complex internal structures,” Annals of nuclear energy, vol. 63, pp. 399-408, 2014.
[Bibtex]
@article{buchan2013,
title = "The immersed body supermeshing method for modelling reactor physics problems with complex internal structures",
journal = "Annals of Nuclear Energy",
volume = "63",
number = "0",
pages = "399--408",
year = "2014",
doi = "10.1016/j.anucene.2013.07.044",
author = "A. G. Buchan and P. E. Farrell and G. J. Gorman and A. J. H. Goddard and M. D. Eaton and E. T. Nygaard and P. L. Angelo and R. P. Smedley-Stevenson and S. R. Merton and P. N. Smith",
}
[7] [doi] P. E. Farrell, M. D. Piggott, C. C. Pain, G. J. Gorman, and C. R. G. Wilson, “Conservative interpolation between unstructured meshes via supermesh construction,” Computer methods in applied mechanics and engineering, vol. 198, iss. 33-36, pp. 2632-2642, 2009.
[Bibtex]
@article{farrell2009a,
author = {Farrell, P. E. and Piggott, M. D. and Pain, C. C. and Gorman, G. J and C. R. G. Wilson},
title = {Conservative interpolation between unstructured meshes via supermesh construction},
journal = {Computer Methods in Applied Mechanics and Engineering},
volume = {198},
number = {33-36},
pages = {2632-2642},
year = {2009},
doi = {10.1016/j.cma.2009.03.004},
}

 

Automated derivation of adjoint models

We typically write down the laws of physics as partial differential equations. These equations propagate causality. You put in some causes such as the shape of an aeroplane, or the weather today, and the equations propagate effects – telling you how well the aeroplane flies or the weather tomorrow.

Now, associated with every such equation (the forward equation) is associated another equation, the adjoint equation, which propagates causality backwards: it maps in a linear way from effects back to their causes. Adjoints are useful because they allow us to design backwards from a desired end goal, rather than forwards by trial and error, and have very important applications across the whole of computational science and engineering. These adjoint equations are important because they tell you how to improve your design: instead of asking, ‘what is the drag coefficient of this wing?’, the adjoint lets you ask, ‘what is the wing shape that has the best drag coefficient?’.

While deriving the adjoint model associated with a linear stationary forward model is straightforward, the derivation and implementation of adjoint models for nonlinear time-dependent models is notoriously difficult. I lead the development of dolfin-adjoint, a software package that solves this problem by automatically analysing and exploiting the high-level mathematical structure inherent in finite element methods [1]. It is implemented on top of the FEniCS Project for finite element discretisations. This software has been used in several varied applications, including the optimisation of arrays of tidal turbines [2], generalised stability analysis [3], variational data assimilation in glaciology [4], topology optimisation of structures under load [5], inverse problems in elastodynamics, cardiac electrophysiology and cardiac electromechanics [6].

For this work, I was awarded the 2015 Wilkinson Prize for Numerical Software.

[1] [doi] P. E. Farrell, D. A. Ham, S. W. Funke, and M. E. Rognes, “Automated derivation of the adjoint of high-level transient finite element programs,” SIAM Journal on Scientific Computing, vol. 35, iss. 4, p. C369–C393, 2013.
[Bibtex]
@article{farrell2012b,
author = {Farrell, P. E. and Ham, D. A. and Funke, S. W. and Rognes, M. E.},
title = {Automated derivation of the adjoint of high-level transient finite element programs},
journal = {{SIAM Journal on Scientific Computing}},
volume = {35},
number = {4},
pages = {C369--C393},
year = {2013},
doi = {10.1137/120873558}
}
[2] [doi] S. W. Funke, P. E. Farrell, and M. D. Piggott, “Tidal turbine array optimisation using the adjoint approach,” Renewable Energy, vol. 63, pp. 658-673, 2014.
[Bibtex]
@article{funke2014a,
title = "Tidal turbine array optimisation using the adjoint approach",
journal = {{Renewable Energy}},
volume = "63",
number = "0",
pages = "658--673",
year = "2014",
doi = "10.1016/j.renene.2013.09.031",
author = "S. W. Funke and P. E. Farrell and M. D. Piggott",
}
[3] [doi] P. E. Farrell, C. J. Cotter, and S. W. Funke, “A framework for the automation of generalised stability theory,” SIAM Journal on Scientific Computing, vol. 36, iss. 1, 2014.
[Bibtex]
@article{farrell2012c,
journal = {{SIAM Journal on Scientific Computing}},
author = {P. E. Farrell and C. J. Cotter and S. W. Funke},
title = {A framework for the automation of generalised stability theory},
volume = {36},
number = {1},
doi = {10.1137/120900745},
year = {2014},
}
[4] [doi] D. J. Brinkerhoff and J. V. Johnson, “Data assimilation and prognostic whole ice sheet modelling with the variationally derived, higher order, open source, and fully parallel ice sheet model VarGlaS,” The Cryosphere, vol. 7, iss. 4, pp. 1161-1184, 2013.
[Bibtex]
@article{brinkerhoff2013,
AUTHOR = {Brinkerhoff, D. J. and Johnson, J. V.},
TITLE = {Data assimilation and prognostic whole ice sheet modelling with the variationally derived, higher order, open source, and fully parallel ice sheet model {VarGlaS}},
JOURNAL = {{The Cryosphere}},
VOLUME = {7},
YEAR = {2013},
NUMBER = {4},
PAGES = {1161--1184},
DOI = {10.5194/tc-7-1161-2013}
}
[5] K. E. Jensen, “Optimising stress constrained structural optimisation,” in Proceedings of the 23rd International Meshing Roundtable, London, UK, 2014.
[Bibtex]
@inproceedings{jensen2014,
address = {London, UK},
booktitle = {{Proceedings of the 23rd International Meshing Roundtable}},
organisation = {Sandia National Laboratory},
author = {K. E. Jensen},
title = {Optimising stress constrained structural optimisation},
year = {2014},
}
[6] G. Balaban, J. Sundnes, M. S. Alnæs, and M. E. Rognes, “Least squares fitting of a cardiac hyperelasticity model using an automatically derived adjoint equation,” in Proceedings of NSCM-27: the 27th Nordic Seminar on Computational Mechanics, 2014, pp. 272-275.
[Bibtex]
@inproceedings{balaban2014,
title = {Least squares fitting of a cardiac hyperelasticity model using an automatically derived adjoint equation},
booktitle = {{Proceedings of NSCM-27: the 27th Nordic Seminar on Computational Mechanics}},
year = {2014},
pages = {272--275},
organisation = {KTH Stockholm Royal Institute of Technology},
author = {G. Balaban and J. Sundnes and M. S. Aln{\ae}s and M. E. Rognes},
editor = {A. Eriksson and A. Kulachenko and M. Mihaescu and G. Tibert}
}