Homotopy methods for differential algebra (M/F)

The thesis will be carried out at the LIX laboratory (Laboratoire d'Informatique de l'École polytechnique), which is located in the Alan Turing building, 1, rue Honoré d'Estienne d'Orves, Palaiseau. The thesis will be carried out in the MAX team and financed by the ANR PRME NODE project. The candidate will be provided with a workstation and the means to attend a few conferences per year.

How to predict planetary motion, the spread of an epidemic, or the evolution of a chemical reaction network? Here are some of the many problems that can be modeled by ordinary differential equations (ODEs). The resolution of such equations has a long history and remains an important problem in science and technology.

Differential algebra is a branch of both mathematics and computer science that is concerned with the study of differential equations from a symbolic and computational point of view. The idea is to use the algebraic methods like rewriting or variable elimination to simplify or transform differential equations. Consider, for example, the statement “there is a linear dependence between functions y1(z) ,y2(z) ,y3(z) with constant coefficients”. This statement can be written as

∃ c1, c2, c3, (c1 ≠ 0 ∨ c2 ≠ 0 ∨ c3 ≠ 0) ∧ c1 y1 + c2 y2 + c3 y3 = 0.

Fundamental theorems in differential algebra guarantee that the existential quantifier can be eliminated: the condition can be expressed as a logical combination of equations and inequations involving only y1, y2, y3. In this case, the condition is indeed equivalent to the vanishing of the Wronskian of y1, y2, y3.

Furthermore, algorithms have been developed and implemented for this kind of quantifier elimination and other fundamental tasks from differential algebra.

The traditional approach to differential algebra is to reason on the differential equations themselves as symbolic expressions. One of the drawback of this approach is that the intermediate results of computation may be really large expressions (imagine differentiating the product y1(z) y2(z) y3(z) ten times!). The aim of the present proposal is to systematically work with power series solutions instead. Such solutions are uniquely determined by the differential equations and a sufficient number of initial conditions. For instance, the power series solutions of y'' + (y')^2 = 0 are y_(α,β)(z) ≔ α + log (1+β z) = α + βz - 1/2 β^2 z^2 + ⋯, with initial conditions y_(α,β)(0)=α, y_(α,β)'(0)=β. Inversely, any differential equation of which y_(α,β) is a solution is a logical consequence of y''+(y')^2=0.

Using this point of view, systems of differential equations give rise to systems of algebraic equations on power series coefficients. For instance, the equation y'' + (y')^2=0 in y = y0 + y1 z + y2 z^2+⋯ is equivalent to the infinite system of equations 2 y2 + y1^2 = 6 y3 + 4 y1 y2 = 12 y4 + 6 y1 y3 + 4 y2^2 = ⋯ = 0 in y0, y1, …. Truncations of such systems can be solved using numerical homotopies. This means that we study the effect of small perturbations of the initial conditions α,β on the solution y_(α,β). We may also consider deformations of the equations themselves into equations that are typically easier to solve.

When successful, numeric homotopy techniques allow us to determine numeric power series solutions for our original system of differential equations. A final challenge is to recover the simplest differential equation(s) of which these numeric power series are the solution. This typically yields a simplification of the original system of differential equations or new equations that do not involve some of the unknown functions. We plan to combine homotopy continuation and sparse interpolation techniques in order to compute differential equations satisfied by power series solutions.

In summary, the main objective of the thesis is to build a bridge between differential algebra and numerical descriptions of sets of power series solutions to differential equations. This bridge should be as effective as possible and lead to new, more efficient algorithms for typical problems from differential algebra, such as the simplification of systems of differential equations, quantifier elimination, uncovering hidden constraints, or the identification of parameters. Depending on her or his profile, the candidate may put higher focus on the more theoretical or practical aspects of this program.

Master students majoring in computer science or mathematics may apply. Knowledge in at least one of the following topics is required: complexity theory, differential calculus, commutative algebra, computer algebra. General programming skills are required to contribute to efficient implementations. Previous experience in differential algebra, homotopy methods and/or sparse interpolation would be a plus.