Description du sujet de thèse

--- Description ---

Both in computer algebra and in numerical analysis, the resolution of systems of polynomial equations is a central problem. In computer algebra, this problem is often tackled using rewriting techniques, such as the computation of Gröbner bases or regular chains. In numerical analysis, one of the most successful methods is based on numerical homotopies. The idea is quite simple and goes as follows.

Starting with an input system, one first constructs a “simpler” system with the “same characteristics”. For instance, given the system
P_1(x,y) = x^2 - y^2 + x + 3 = 0
P_2(x,y) = x^2 + 2 x y + 7 y^2 - 8 y + 2 = 0, (1)
we may for instance take
Q_1(x,y) = x^2 - α_1 = 0 (α_1 = 1 + i)
Q_2(x,y) = y^2 - α_2 = 0 (α_2 = 2 - i). (2)
for our simpler system. Both systems indeed have the “same characteristics” in the sense that deg Q_1=deg P_1=2 and deg Q_2=deg P_2=2. In particular, we expect both systems to admit the same number of solutions. By construction, the solutions
(x,y) ∈ {(sqrt(α_1), sqrt(α_2)), (sqrt(α_1), -sqrt(α_2)), (-sqrt(α_1), sqrt(α_2)), (-sqrt(α_1), -sqrt(α_2))} of (2) are easy to compute. Now the main idea is to continuously deform the second system into the first system using a homotopy continuation:
H_1^t (x,y) = (1-t) P_1(x,y) + t Q_1(x,y) = 0
H_2^t (x,y) = (1-t) P_2(x,y) + t Q_2(x,y) = 0. (3)
Indeed, at t=1 and t=0, the homotopy system (3) reduces to (2) and (1), respectively. In order to obtain the solutions of (1), it thus suffices to follow the solutions of (3) from t=1 until t=0, using standard numerical algorithms. For instance, knowing the approximate solutions of (1) at a given time t=t_0, we may find approximate solutions at t=t_0+δ using Newton's method, starting with the approximations at t=t_0 as our ansatz. It is also possible to design higher order (e.g. Euler-type) methods, which allow us to
take larger steps δ.

--- Context ---

There is an extensive literature on numeric homotopies. Practical problems are usually not generic, which means that there may be multiple solutions or solution paths z(t) that go to infinity (i.e. there are less isolated solutions than predicted by the Bézout bound). Special strategies, called end-games, need to be used near t=0 to cope with multiple solutions. Solution paths that go to infinity typically occur for sparse systems, when the supports of the polynomial P_k are special. Refinements of the Bézout bound exist for this situation and special homotopies can be constructed that preserve the support properties and the predicted number of solutions by this refined bound. Finally, there exist several techniques to certify the numeric solutions at t=0 or all along the path.

In favorable cases, existing software for numeric homotopies is many times faster than symbolic software for the computation of Gröbner bases. However, many things can go wrong during numeric path tracking: there might be singularities on or near the paths, end-games for high multiplicities may incur a large performance penalty, the working precision might be insufficient, the numeric conditioning might be bad, etc. Existing software packages typically require manual fine-tuning of internal parameters in order to treat the most interesting examples.

In the context of the ERC ODELIX project (of which this proposal is a part), we are interested in polynomial systems that are verified by the coefficients of truncated power series solutions of differential equations. Such systems come with a special structure that we wish to understand better and then exploit.

--- Methodology ---

The thesis will begin by gathering state of the art literature on numerical polynomial system solving, along with software implementation. We will focus on the case of square homogeneous systems with regular solutions. More specifically, the following theoretical question will be addressed: How to perform reliable homotopy continuations in the most efficient way?

The second part of the thesis will be devoted to non-regular solutions (what are the most efficient methods to numerically compute multiple zeros and certify them?) and systems that arise from differential equations (how to exploit this special structure and what is the complexity of homotopy continuation for this application?).

The practical component of the thesis concerns the software implementation of reliable homotopy methods. We intend to distribute the implementation inside a dedicated library as free software under the GNU General Public License. Several tools for reliable arithmetic are already available in Mathemagix, which may potentially be used for the implementation work.

More specifically, we plan to work on the following implementation issues:
• Development of algorithms for the efficient evaluation of the input polynomials for various numerical and reliable data types, possibly using automatic code generation and just-in-time compilation.
• Implementation of additional reliable data types for the efficient certification of numeric homotopy steps, such as special kinds of Taylor models and ball arithmetic.
• Development of multi-threaded homotopy solvers.
• Make the homotopy solvers benefit from hardware SIMD (Single Instruction Multiple Data) vector instructions, potentially based on tools available in the Mathemagix system.

Contexte de travail

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 ERC ODELIX project. The candidate will be provided with a workstation and the means to attend a few conferences per year.

Contraintes et risques

None.

Informations complémentaires

The project will be financed by the ERC ODELIX project.