Title: Numeric-symbolic polynomial system solving

Topics: symbolic and numeric algorithms, polynomial system solving, complexity

Address

Research team: MAX, Algebraic modeling and symbolic computation

Contacts

Context

The MAX team is searching for PhD candidates on the themes of the “ODELIX” ERC Advanced Grant. The present M2 internship proposal allows applicants to familiarize themselves with these themes. Upon successful completion of the internship, there will be an opportunity to pursue with a PhD.

Applying

Applications can be sent by email to the above contact persons; they should include a CV, a transcript of records, a letter of motivation, and optional recommendation letters. Note that we have no hard deadlines; new applications will be considered at any time of the year, as long as the Odelix project runs.

The resolution of algebraic systems is a flagship tool for computer algebra, with many applications in robotics, chemistry, signal, cryptology, etc. The complexity bounds have been mostly studied in worst cases, and they turn out to be often very pessimistic. It is therefore necessary, for a given problem, to take advantage of its specific features.

For rational number coefficient systems, the numeric methods behave well in practice for sufficiently generic input systems, and have been a very active research topic for fifty years. Popular methods proceed by deformations. First, one chooses a system of a geometric nature close to the system to be solved and from which one can determine solutions quickly. Then, one deforms the system so that be able to update solutions efficiently and finally arrive at those of the input system. In the numeric framework, certifying the solution set is a tedious problem. At least certifying regular isolated solutions turns out to be rather easy and efficient in practice.

This internship will focus on the certification of solutions that are not necessarily isolated or regular. A first objective will be to deepen the knowledge of algebraic geometry and numerical calculation necessary for understanding algorithms by deformation [1, 7, 6]. The second objective will concern practical tools used to certify numeric calculations. One popular approach to reliable computation is to use interval or ball arithmetic [3, 5, 4]. This amounts to systematically replace any floating point approximation of a real number by an interval that is certified to contain the exact value . Then, the main part of the internship will concern comparisons of certification algorithms of solutions [2, 8, 9]. The algorithms will be implemented in the Mathemagix framework (http://www.mathemagix.org), that already contains the necessary basic data structures (balls, polynomials, series, matrices).

We seek for excellent candidates with a background both in mathematics and computer science. Applicants will be required to have knowledge in algebra, algorithms, and complexity. Programming skills will be useful to achieve efficient implementations.