2017
How many operations do we need on the average to compute an approximate root of a random Gaussian polynomial system? Beyond Smale's 17th problem that asked whether a polynomial bound is possible, we prove a quasi-optimal bound $\text{(input size)}^{1+o(1)}$. This improves upon the previously known $\text{(input size)}^{\frac32 +o(1)}$ bound.
The new algorithm relies on numerical continuation along rigid continuation paths. The central idea is to consider rigid motions of the equations rather than line segments in the linear space of all polynomial systems. This leads to a better average condition number and allows for bigger steps. We show that on the average, we can compute one approximate root of a random Gaussian polynomial system of $n$ equations of degree at most $D$ in $n+1$ homogeneous variables with $O(n^5 D^2)$ continuation steps. This is a decisive improvement over previous bounds that prove no better than $\sqrt{2}^{\min(n, D)}$ continuation steps on the average.
2017
w/ P. Bürgisser and F. Cucker
Baisc semialgebraic sets are the parts of $\mathbb{R}^n$ that are defined by the conjunction of polynomial inequalities. They may have very different shapes and homology is a prominent tool to describe them. Nevertheless, the computation of the homology is challenging. So far, only double exponential complexity algorithms are known, with respect to the number of variables. That is, we can compute the homology of a semialgebraic set defined by $s$ polynomial equations and inequalities of degree $D$ in $n$ variables in $(sD)^{2^{O(n)}}$.
In “Computing the homology of basic semialgebraic sets in weak exponential time”, we design a numerical algorithm for this problem and we show that its complexity is $\big( (s+n)D / \delta \big)^{O(n^2)}$ where $\delta$ is related to the distance of the input equations to numerically ill-posed problems (which happens when infinitesimal pertubations of the input problem cause topological modifications). Furthermore, we provide probabilistic analysis of this complexity.
The method is to approximate the semialgebraic set with a cloud of points. If the cloud is close enough to the set and dense enough, then it allows to recover all the relevant information about the topology of the set.
2016
w/ T. Vaccon
P-adic numbers often appears in computer algebra when one want to solve a problem over a finite field $\mathbb F_p$ using an algorithm that performs divisions by $p$: we consider the data over the finite field as the approximation of some exact $p$-adic numbers, proceed to the computation over the field of $p$-adic numbers and then we obtain the result back in $\mathbb F_p$ by reducing modulo $p$. Naturally, we cannot compute with $p$-adic numbers with infinite precision, for the same reason as for real numbers. So we have to deal with approximations, and this raises questions about the numerical stability of algorithms when they are run with $p$-adic numbers.
In “On p-adic differential equations with separation of variables”, we study the problem of computing a power series solution to an ordinary differential equation. We show that the usual Newton method achieve the optimal loss of precision, this allows for a significant speedup.
2015
The orbit of a polynomial $P(x_1,\dotsc,x_n)$ is the set of all polynomials obtained from $P$ by invertible linear changes of variables. The boundary of the orbit of $P$ is the set of limit points of the orbit that are not in the orbit itself. For example, the polynomial $12y(yz+x^2)$ is in the boundary of the orbit of the polynomial $P(x,y,z) = yz^2 -x^3$ because
In “The boundary of the orbit of the 3 by 3 determinant polynomial”, we describe the boundary of the orbit of the 3x3 determinant polynomial, $\det_3(x_1,\dotsc, x_9)$. It has two irreducible components: the closures of the orbits of the polynomials $\det_3(x_1,\dotsc, x_8, -x_1-x_5)$ and $x_4 \cdot x_1^2 + x_5\cdot x_2^2 + x_6\cdot x_3^2 + x_7\cdot x_1x_2 + x_8\cdot x_2x_3 + x_9\cdot x_1x_3$.
The 3x3 determinant polynomial
Algorithms to compute discrete sums are well studied since Zeilberger coined the method of creative telescoping. The range of applications of these algorithms is wide, but they are not yet entirely satisfactory: to prove an identity, the help of algorithms is decisive but it is often the case that algorithm cannot conclude alone, without human insight.
In “Multiple binomial sums”, we define a class of discrete sums, called multiple binomial sums, and we describe an efficient algorithm that can prove or disprove that two given such sums are equal. The algorithm relies on the computation of periods of rational integral. From a mathematical point of view, multiple binomial sums have very interesting properties: it turns out that that they are exactly the diagonals of rational functions.
All the algorithms we describe are implemented in the Maple package BinomSums.
Andrews-Paule identity, an equality between two binomial sums.
2015
w/ P. Bürgisser, K. Kohn and B. Sturmfels
It is well known that lines of the projective space $\mathbb P^3$ — or equivalently, 2-dimensional subspaces of a 4-dimensional vector space — are parametrized by a projective variety of dimension four, the Grassmannian $G(2,4)$. And Plücker coordinates realize this variety as a quadric of $\mathbb P^5$. What about the parametrization curves of degree two in $\mathbb P^3$? Celebrated predecessors — Cayley, van der Waerden, Green, Morrison, Gel’fand, Kapranov, Zelevinsky, etc. — have shown how to realize this parametrization as a 8-dimensional subvariety of $\mathbb P^{19}$: the Chow variety of quadratic space curves.
In “Computing the Chow variety of quadratic space curves”, we performed the computations all the way through to give the explicit equations. For example, we obtain that the two components of the Chow variety of quadratic space curves have degree 140 and 92.
2015
For numerically solving polynomial system of equation, the method of homotopy continuation is widely used. They are a lot of questions related to its computational complexity, the first of which is Smale's 17th problem. In a recent breakthrough, Berltrán and Pardo have shown how to achieve a polynomial average complexity with a probabilistic algorithm. The last obstacle that remains concerning Smale's 17th problem is to find a determinitic algorithm. It is precisely what I do in “A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time”. This gives an answer to Smale's 17th problem, in the strongest sense.