6 papers
Computing points in connected components defined by a real inequation: algorithms, complexity and implementations, Part I
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…
Probabilistic algorithm for computing all local minimizers of Morse functions on a compact domain
Mohab Safey El Din, Georgy Scholten, Emmanuel Trélat
Let K be the unit-cube in Rn and f\,: K 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 ev…
A complexity analysis of the F4 Gröbner basis algorithm with tracer data
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 pr…
On Exact Reznick, Hilbert-Artin and Putinar's Representations
Victor Magron, Mohab Safey El Din
We consider the problem of computing exact sums of squares (SOS) decompositions for certain classes of non-negative multivariate polynomials, relying on semidefinite programming (S…
Computing roadmaps in unbounded smooth real algebraic sets II: algorithm and complexity
Rémi Prébet, Mohab Safey El Din, Ãric Schost
A roadmap for an algebraic set defined by polynomials with coefficients in the field of rational numbers is an algebraic curve contained in whose intersection…
Refined bit complexity for the computation of at least one point per connected component of a smooth complete intersection real algebraic set
Jesse Elliott, Mark Giesbrecht, Edern Gillot +2
We refine the bit complexity analysis of an algorithm for the computation of at least one point per connected component of a smooth real algebraic set, yielding exponential speedup…