13 citations · 63 across the 21 of their papers we have counts for
22 papers · 1 filter
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…
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…
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…
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…
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…
Critical Points and Gröbner Bases: the Unmixed Case
Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer
We consider the problem of computing critical points of the restriction of a polynomial map to an algebraic variety. This is of first importance since the global minimum of such a…
On the Complexity of the Generalized MinRank Problem
Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer
We study the complexity of solving the \emph{generalized MinRank problem}, i.e. computing the set of points where the evaluation of a polynomial matrix has rank at most . A natu…
Gröbner Bases of Bihomogeneous Ideals generated by Polynomials of Bidegree (1,1): Algorithms and Complexity
Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer
Solving multihomogeneous systems, as a wide range of structured algebraic systems occurring frequently in practical problems, is of first importance. Experimentally, solving these…