2020
w/ P. Bürgisser and F. Cucker
In “Rigid continuation paths II”, we develop an algorithm to compute an approximate zero of a polynomial system given as a black-box evaluation function. It follows the main lines of the algorithm from Part I but with a probabilistic estimation of the step length for the numerical continuation.
Going a step further, we show that, on average, the algorithm behaves well on a universal family of polynomial system with low evaluation cost. More precisely, we introduce the model of Gaussian random algebraic branching program and show that our algorithm performs $\operatorname{poly}(n, \delta)$ operations on average to solve a random ABP in $n$ variables, of degree $\delta$ and of size $\operatorname{poly}(n, \delta)$.
2018
w/ E. Sertöz
In “A transcendental method in algebraic geometry”, Griffiths emphasized the role of certain multivariate integrals, known as periods, “to construct a continuous invariant of arbitrary smooth projective varieties”. Periods often determine the projective variety completely and therefore its algebraic invariants. Translating periods into discrete algebraic invariants is a difficult problem, exemplified by the long standing Hodge conjecture which describes how periods determine the algebraic cycles within a projective variety.
Recent progress in computer algebra makes it possible to compute periods with high precision and put transcendental methods into practice. We focus mainly on algebraic surfaces and give a numerical method to compute Picard groups. As an application, we count smooth rational curves on quartic surfaces using the Picard group.
A K3 surface containing 133056 smooth rational curves of degree 4 generating a Picard group of rank 19.
2018
Hermite reduction is a classical algorithmic tool in symbolic integration. It is used to decompose a given rational function as a sum of a function with simple poles and the derivative of another rational function.
We extend Hermite reduction to arbitrary linear differential operators instead of the pure derivative, and develop efficient algorithms for this reduction. We then apply the generalized Hermite reduction to the computation of linear operators satisfied by single definite integrals of D-finite functions of several continuous or discrete parameters. The resulting algorithm is a generalization of reduction-based methods for creative telescoping.
A classical identity relating Chebyshev polynomials with Bessel functions
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
Basic 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
\[P\big(4\epsilon^2 x- \epsilon y, -\epsilon^3 y, -6 \epsilon x + y - 6\epsilon^2 z\big) = 12y(yz+x^2) \epsilon^5 + \mathcal{O}(\epsilon^6).\]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.