13 citations · 63 across the 21 of their papers we have counts for
28 papers
Refined complexity bounds for rational reconstruction and XGCD through Padé approximants and Cauchy interpolants
Vincent Neiger, Mohab Safey El Din, Kevin Tran
When computing with univariate polynomials, two fundamental and related problems are the XGCD and rational reconstruction, classically solved in quasi-linear complexity using the h…
Convergence rate of the moment-SOS hierarchy for univariate polynomial optimization
Didier Henrion, Mohab Safey El Din
We study the convergence rate of the moment-SOS (sum-of-squares) hierarchy for polynomial optimization problems (POPs) on a bounded subset of the real line described by arbitrary p…
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…
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…
Algebraic Proofs of Path Disconnectedness using Time-Dependent Barrier Functions
Didier Henrion, Jared Miller, Mohab Safey El Din
Two subsets of a given set are path-disconnected if they lie in different connected components of the larger set. Verification of path-disconnectedness is essential in proving the…
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…
Algebraic certificates for the truncated moment problem
Didier Henrion, Simone Naldi, Mohab Safey El Din
The truncated moment problem consists of determining whether a given finitedimensional vector of real numbers y is obtained by integrating a basis of the vector space of polynomial…
On the degree of varieties of sum of squares
Andrew Ferguson, Giorgio Ottaviani, Mohab Safey El Din +1
We study the problem of how many different sums of squares decompositions a general polynomial with SOS-rank admits. We show that there is a link between the variety $\math…
Computing roadmaps in unbounded smooth real algebraic sets I: connectivity results
Rémi Prébet, Mohab Safey El Din, Éric Schost
Answering connectivity queries in real algebraic sets is a fundamental problem in effective real algebraic geometry that finds many applications in e.g. robotics where motion plann…
A Signature-based Algorithm for Computing the Nondegenerate Locus of a Polynomial System
Christian Eder, Pierre Lairez, Rafael Mohr +1
Polynomial system solving arises in many application areas to model non-linear geometric properties. In such settings, polynomial systems may come with degeneration which the end-u…
New efficient algorithms for computing Gröbner bases of saturation ideals (F4SAT) and colon ideals (Sparse-FGLM-colon)
Jérémy Berthomieu, Christian Eder, Mohab Safey El Din
This paper is concerned with linear algebra based methods for solving exactly polynomial systems through so-called Gröbner bases, which allow one to compute modulo the polynomial i…
Solving parametric systems of polynomial equations over the reals through Hermite matrices
Huu Phuoc Le, Mohab Safey El Din
We design a new algorithm for solving parametric systems having finitely many complex solutions for generic values of the parameters. More precisely, let $f = (f_1, \ldots, f_m)\su…
Guessing Gr{ö}bner Bases of Structured Ideals of Relations of Sequences
Jérémy Berthomieu, Mohab Safey El Din
Assuming sufficiently many terms of a n-dimensional table defined over a field are given, we aim at guessing the linear recurrence relations with either constant or polynomial coef…
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…
Bit complexity for multi-homogeneous polynomial system solving Application to polynomial minimization
Mohab Safey El Din, Eric Schost
Multi-homogeneous polynomial systems arise in many applications. We provide bit complexity estimates for solving them which, up to a few extra other factors, are quadratic in the n…
Exact algorithms for linear matrix inequalities
Didier Henrion, Simone Naldi, Mohab Safey El Din
Let be a linear matrix, or pencil, generated by given symmetric matrices of size with rational entries. The set of real v…
Real root finding for low rank linear matrices
Didier Henrion, Simone Naldi, Mohab Safey El Din
We consider matrices (with ) in a real affine subspace of dimension . The problem of finding elements of low rank in such spaces finds many applications in…
Real root finding for determinants of linear matrices
Didier Henrion, Simone Naldi, Mohab Safey El Din
Let $\A_0, \A_1, \ldots, \A_n$ be given square matrices of size with rational coefficients. The paper focuses on the exact computation of one point in each connected component…
On the complexity of computing Gröbner bases for weighted homogeneous systems
Jean-Charles Faugère, Mohab Safey El Din, Thibaut Verron
Solving polynomial systems arising from applications is frequently made easier by the structure of the systems. Weighted homogeneity (or quasi-homogeneity) is one example of such a…
Computing necessary integrability conditions for planar parametrized homogeneous potentials
Alin Bostan, Thierry Combot, Safey El Din Mohab
Let $V\in\mathbb{Q}(i)(\a_1,\dots,\a_n)(\q_1,\q_2)$ be a rationally parametrized planar homogeneous potential of homogeneity degree . We design an algorithm that co…
Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
Aurélien Greuet, Mohab Safey El Din
Let $f, f_1, \ldots, f_\nV$ be polynomials with rational coefficients in the indeterminates $\bfX=X_1, \ldots, X_n$ of maximum degree and be the set of common complex solut…
A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets
Mohab Safey El Din, Eric Schost
A roadmap for a semi-algebraic set is a curve which has a non-empty and connected intersection with all connected components of . Hence, this kind of object, introduced by C…
Intrinsic complexity estimates in polynomial optimization
Bernd Bank, Marc Giusti, Joos Heintz +1
It is known that point searching in basic semialgebraic sets and the search for globally minimal points in polynomial optimization tasks can be carried out using ar…
A probabilistic algorithm to compute the real dimension of a semi-algebraic set
Mohab Safey El Din, Elias Tsigaridas
Let $\RR$ be a real closed field (e.g. the field of real numbers) and $\mathscr{S} \subset \RR^n$ be a semi-algebraic set defined as the set of points in $\RR^n$ satisfying a syste…