Mohab Safey El Din

Mohab Safey El Din, Georgy Scholten, Emmanuel Trélat

Let K be the unit-cube in Rn and f\,: K $\rightarrow$ R^n be a Morse function. We assume that the function f is given by an evaluation program $Γ$ in the noisy model, i.e., the evaluation program $Γ$ takes an extra parameter $η$ as input and returns an approximation that is $η$-close to the true value of f . In this article, we design an algorithm able to compute all local minimizers of f on K . Our algorithm takes as input $Γ$, $η$, a numerical accuracy parameter $ε$ as well as some extra regularity parameters which are made explicit. Under assumptions of probabilistic nature -- related to the choice of the evaluation points used to feed $Γ$ --, it returns finitely many rational points of K , such that the set of balls of radius $ε$ centered at these points contains and separates the set of all local minimizers of f . Our method is based on approximation theory, yielding polynomial approximants for f , combined with computer algebra techniques for solving systems of polynomial equations. We provide bit complexity estimates for our algorithm when all regularity parameters are known. Practical experiments show that our implementation of this algorithm in the Julia package Globtim can tackle examples that were not reachable until now.

Elisabetta Rocchi, Mohab Safey El Din

Connected components of real algebraic sets are semi-algebraic, i.e. they are described by a boolean formula whose atoms are polynomial constraints with real coefficients. Computing such descriptions finds topical applications in optical system design and robotics. In this paper, we design a new algorithm for computing such semi-algebraic descriptions for real algebraic curves. Notably, its complexity is less than the best known one for computing a graph which is isotopic to the real space curve under study.

Robin Kouba, Vincent Neiger, Mohab Safey El Din

We provide a new complexity bound for the computation of grevlex Gröbner bases in the generic zero-dimensional case, relying on Moreno-Socías' conjecture. We first formalize a property of regular sequences that implies a well-known folklore consequence, which we call the increasing degree property. We then derive a new understanding of the selection of pairs in the F4 algorithm based on Moreno-Socías' conjecture. Moreover, we obtain an exact formula for the number of elements in the grevlex Gröbner basis of a given degree, for half of the relevant degrees. Combining these results, we derive a precise complexity formula for the F4 Tracer algorithm, together with its asymptotic behavior when the number of variables tends to infinity. These results yield an improvement over the state-of-the-art complexity bounds by a factor which is exponential in the number of variables.

Jérémy Berthomieu, Edern Gillot, Mohab Safey El Din

We consider the problem of computing sample points in each connected component of a semi-algebraic set defined by the non-vanishing or the positivity of an n-variate polynomial of degree d, with rational coefficients of bit size bounded by $τ$. Such a problem is a basic routine in effective real algebraic geometry, used in higher-level algorithms for solving polynomial systems over the reals and finds many applications in sciences. We design a probabilistic algorithm for solving this problem, which is based on reductions to different routines for solving zero-dimensional polynomial systems. It assumes that the input polynomial satisfies sufficiently generic properties (namely, smoothness of its defining hypersurface). This is done through the computations of critical points of well-chosen maps to capture the connected components of the semi-algebraic set under study. We derive a bit complexity estimate for the cost of this algorithm, which is, in terms of the B{é}zout bound d(d -1)^{n-1}, essentially cubic for obtaining parametrisations of the sought-for real points. Moreover, we also consider the case of obtaining rational approximations of those points, which are precise enough to lie in the same connected components as their exact counterparts, which yields a cost that is essentially quartic in the B{é}zout bound. In these complexity estimates, we take into account the degree structure of the input polynomial and its partial derivatives, allowing for a more refined bit complexity when the partial derivative of the input polynomial have degree lower than expected. We also analyse the probability of success of those algorithms. We report on practical experiments, benchmarking with random dense input polynomials as well as polynomials coming from applications, which were out of reach of the state-of-the-art implementations, and hence illustrate the practical efficiency of these new algorithms.