Homotopy methods for differential algebra (M/F)

Job Description

Thesis Subject

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 mathematics that is concerned with the study of differential equations from an algebraic and symbolic point of view. Its general philosophy is to equip the resolution of differential equations with a general framework, similarly to algebraic geometry providing foundations for polynomial system solving. On the constructive side, the idea is to use 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 y₁(z), y₂(z), y₃(z) with constant coefficients”. This statement can be written as:

∃c₁, c₂, c₃, (c₁ ≠ 0 ∨ c₂ ≠ 0 ∨ c₃ ≠ 0) ∧ c₁ y₁ + c₂ y₂ + c₃ y₃ = 0.

Similarly to the celebrated result by Tarski for constructible sets, 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 y₁, y₂, y₃. In this case, the condition is indeed equivalent to the vanishing of the Wronskian of y₁, y₂, y₃:

| y₁ y₂ y₃ |
| y₁' y₂' y₃' | = 0
| y₁'' y₂'' y₃'' |

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 drawbacks of this approach is that the intermediate results of computation may be really large expressions (imagine differentiating the product y₁(z) y₂(z) y₃(z) ten times!). An alternative approach could be to work instead with some solutions of the equations of interest. To this end, Seidenberg embedding theorem implies that power series solutions are dense within the set of all solutions with respect to an appropriate topology (called Kolchin topology). Therefore, the aim of the present proposal is to systematically work with power series solutions instead of equations themselves. 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')² = 0 are y_(α,β)(z) ≔ α + log (1 + β z) = α + β z - 1/2 β² z² + ..., with initial conditions y_(α,β)(0) = α, y_(α,β)'(0) = β. Conversely, any differential equation of which y_(α,β) is a solution is a logical consequence of y'' + (y')² = 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')² = 0 in y = y₀ + y₁ z + y₂ z² + ... is equivalent to the infinite system of equations 2 y₂ + y₁² = 0, 6 y₃ + 4 y₁ y₂ = 0, 12 y₄ + 6 y₁ y₃ + 4 y₂² = 0, ... in y₀, y₁, ... Truncations of such systems define algebraic varieties, so the tools from constructive nonlinear algebra can be applied to them. One particularly promising tool is homotopy continuation, which can be presented as a study of 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, homotopy techniques provide a description of the numeric power series solutions for our original system of differential equations by a so-called witness set, and the next step is to extract relevant algebraic information from this description. One typically would like to discover hidden relations between variables (such as the ones appearing for high-index DAEs) or obtain new equations that do not involve some of the unknown functions (such as input-output relations in control theory). Existence of such relations can be typically established by considering the dimension of appropriate projections of the corresponding algebraic varieties.

Finally, even though our main philosophy is to systematically work with solutions instead of equations, it is in theory possible to determine the simplest solutions satisfied by given equations by combining homotopy techniques and sparse interpolation. Sparse interpolation is a general probabilistic technique to reconstruct sparse polynomials x_1^{i_{1, 1}} \cdots x_n^{i_{1, n}} + ... + c_s x_1^{i_{s, 1}} ... x_n^{i_{s, n}} from a suitable number of numerical evaluations. For exact polynomials with rational coefficients, one typically uses modular reduction, followed by evaluations at a geometric progression or FFT points in a finite field. Due to a series of recent improvements, this kind of sparse interpolation technique has become extremely efficient. In the present project, we intend to combine sparse interpolation with homotopy techniques, which means that we rather work with polynomials over the complex numbers. We intend to develop novel techniques to make sparse interpolation very efficient in this context as well.

In summary, the main objective of the thesis is to build a bridge between differential algebra and descriptions of sets of power series solutions to differential equations. This bridge should consist of solid mathematical foundations and be as effective as possible, ultimately leading 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.

Your Work Environment

Differential algebra was initially created as a purely algebraic and constructive theory to reason on systems of differential equations. With the advent of computer algebra, effective counterparts have been developed and implemented. The approach to study differential equations through their power series solutions has a long history, but effective counterparts remain scarce.

Homotopy continuation techniques have led to very efficient solvers for systems of algebraic equations. However, they are typically less robust than algebraic solvers, and the development of solvers that are both reliable and efficient remains an important issue.

Sparse interpolation is an approach to recover sparse polynomials or rational functions from sufficiently many numerical evaluations. Due to a series of recent improvements, it has become very efficient. Its combination with numerical homotopy techniques may both lead to more robust solvers and the reconstruction of algebraic counterparts of numerical solutions.

The work will be co-supervised by Fabrice Rouillier from the OURAGAN team at the Institut de Mathématiques de Jussieu – Paris rive gauche. The candidate will have an office and a computer at the Computer Science Laboratory of École Polytechnique (LIX), within the MAX team (algebraic modeling).

Compensation and benefits

Compensation

2300 € gross monthly

Annual leave and RTT

44 jours

Remote Working practice and compensation

Pratique et indemnisation du TT

Transport

Prise en charge à 75% du coût et forfait mobilité durable jusqu’à 300€

About the offer

About the CNRS

The CNRS is a major player in fundamental research on a global scale. The CNRS is the only French organization active in all scientific fields. Its unique position as a multi-specialist allows it to bring together different disciplines to address the most important challenges of the contemporary world, in connection with the actors of change.

CNRS

The research professions