Fabrice Rouillier

Research Director · Inria Paris research center

Approach

My core work is the design of algorithms for the real solutions of (semi-)algebraic systems that are at the same time

  • universal — they can be applied blindly to any input; a method restricted to a class of systems comes with a test that checks its hypotheses;
  • efficient — they solve problems out of reach of other methods;
  • certified — the output is unambiguous: real roots are separated from complex roots with tiny imaginary parts, approximations come with guaranteed precision, and the algorithm may answer "I don't know" rather than something false.

The classical universal tool, Cylindrical Algebraic Decomposition, has a doubly exponential cost in the number of variables. I mostly follow the other route, synthesized in the 1990s by Basu, Pollack and Roy: nested strategies that reduce everything to zero-dimensional systems, eliminating variables "by blocks" and reaching singly exponential costs. This gives a natural hierarchy of problems, each built on the previous ones:

  1. zero-dimensional systems (finitely many solutions): counting, isolating and approximating the real solutions;
  2. parametric systems (finitely many solutions for almost all parameter values): describing how the solutions depend on the parameters — the bulk of what applications actually ask for;
  3. positive-dimensional systems: deciding emptiness, one point per connected component;
  4. more general problems (quantifier elimination, roadmaps), which I only address in special cases.

Main contributions

Rational Univariate Representation, Descartes, discriminant varieties

Three nested building blocks appear in nearly all my results.

  • The Rational Univariate Representation (RUR) turns a system with finitely many complex solutions into an equivalent one of the form $f(T)=0,\ X_i = f_i(T)/f_0(T)$, a bijection between the solutions and the roots of a single univariate polynomial that preserves multiplicities and real points. AAECC 1999
  • Descartes' method with multi-precision interval arithmetic isolates the real roots of univariate polynomials while avoiding coefficient blow-up; combined with the RUR it isolates the real solutions of zero-dimensional systems in arbitrarily small boxes. J. Comput. Appl. Math. 2004, with P. Zimmermann; quasi-optimal version in ISSAC 2016, with A. Kobel and M. Sagraloff.
  • Discriminant varieties partition the parameter space of a parametric system into cells above which the solutions behave regularly (constant number, analytic covering). Studying this variety is a reasonable definition of solving a parametric system. J. Symbolic Comput. 2007, with D. Lazard.

All three are part of the official Maple distribution, where they are the default solutions for these operations (see Software).

Topology of real plane algebraic curves

A historical subject of computer algebra, at the origin of subresultants, Sturm-like sequences and Cylindrical Algebraic Decomposition. Starting from root isolation and from the need to describe the complement of discriminant varieties, and in collaboration with the Gamble team (Inria Nancy), MPI Saarbrücken and IRMAR, we revisited every step of the bivariate CAD — keeping critical and singular points as two-dimensional information instead of projecting them. This led to state-of-the-art algorithms, both in practice and in complexity, for bivariate system solving, triangular decompositions and curve topology (Discrete Comput. Geom.), where we show that the overall complexity is essentially that of isolating the roots of the discriminant. Certified plotting of such curves (a pixel is lit if and only if the curve crosses it) is often the most useful answer for parametric problems with two parameters. A demonstrator: ISOTOP.

Computation for low-dimensional topology

Within OURAGAN, at the Institut de Mathématiques de Jussieu, computer algebra is used as a research tool for pure mathematics: to build intuition, produce examples and counter-examples, and contribute to proofs. With E. Falbel and P.-V. Koseleff we computed representations of fundamental groups of 3-manifolds into PGL(3,C), in the search for spherical CR structures — a generalisation of Thurston's hyperbolic theory. Together with A. Guilloux and M. Thistlethwaite this led to a theorem on the character variety of the figure-eight knot whose proof is a computation. With P.-V. Koseleff and D. Pecker, we studied Chebyshev parametrisations of knots.

PACE — algebraic computations for engineering

PACE, created in 2025 and which I co-direct with Guillaume Rance (Safran), is the joint laboratory of the OURAGAN project-team and Safran Electronics & Defense. It grew out of our work on parametric systems and of a collaboration that started in 2021 with parallel robots for line-of-sight stabilisation: the same algorithms — Rational Univariate Representations, real root isolation, discriminant varieties, certified Newton iterations with Kantorovich tests — now serve three application areas:

  • robotics — design of parallel mechanisms and certified simulation of their control;
  • robust control theory — stability, $L_\infty$ norms;
  • geolocation.

The laboratory develops an open software ecosystem around the Julia package PACE.jl, backed by the certified C library LACE and usable from Maple and MATLAB (see Software).

Applications and transfer

Applications drive the questions and validate the algorithms. I deliberately restrict them to a few fields, since modelling matters as much as solving — two slightly different models can make a computation easy or impossible:

  • robotics — parallel and serial manipulators: cuspidal robots, design and control of parallel robots, with D. Chablat and P. Wenger (LS2N, Nantes);
  • control theory — stability of multidimensional systems, $L_\infty$-norm computation;
  • mathematics — see above.

About a third of my publications are directly tied to a transfer activity, from CMW Marioni (1997) to Safran Electronics & Defense — first contracts in 2021, now the joint laboratory PACE — and through a long-term collaboration with Waterloo Maple Inc.

Representative publications

  • My most cited paper: F. Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. Applicable Algebra in Engineering, Communication and Computing, 9(5):433–461, 1999. HAL
  • The one that required the most work before publishing anything: E. Falbel, P.-V. Koseleff, F. Rouillier. Representations of fundamental groups of 3-manifolds into PGL(3,C): exact computations in low complexity. Geometriae Dedicata 177, 2015. arXiv
  • A broad collaboration on a highly competitive problem: D. N. Diatta, S. Diatta, F. Rouillier, M.-F. Roy, M. Sagraloff. Bounds for polynomials on algebraic numbers and application to curve topology. Discrete & Computational Geometry. arXiv

Current directions

  • Polynomial system solving — revisiting 20-year-old state-of-the-art algorithms with today's building blocks; finding small RURs with number-theoretic tools such as LLL; complex zeros of zero-dimensional systems; over-determined bivariate and trivariate systems; univariate polynomials over towers of number fields.
  • Algebraic–numeric computation — certified evaluation of non-algebraic functions (logarithms, dilogarithms for volumes) at algebraic points; mixing floating-point and exact computation; enclosing objects too large to handle (tubes around curves, convex hulls of real algebraic varieties).
  • Curves and surfaces — topology of parametrised curves in any dimension, visualisation of knots; singularities and silhouettes of surfaces for systems with three parameters.
  • Applications, within PACE — an effective polydisc Nullstellensatz for stability in control theory; design and certified simulation of parallel robots; geolocation.
  • Software — modernising the C libraries (memory management, floating point) and adapting them to multi-threading.