Source author record

Marie-Francoise Roy

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.AG Symbolic Computation Computational Geometry math.AT math.GT

Catalog footprint

Research overview

4works

5topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Divide and Conquer Roadmap for Algebraic Sets

Let $\mathrm{R}$ be a real closed field, and $\mathrm{D} \subset \mathrm{R}$ an ordered domain. We describe an algorithm that given as input a polynomial $P \in \mathrm{D} [ X_{1},\ldots,X_{k} ]$ , and a finite set, $\mathcal{A}= \{ p_{1}, \ldots,p_{m} \}$ , of points contained in $V= \mathrm{Zer}( P, \mathrm{R}^{k})$ described by real univariate representations, computes a roadmap of $V$ containing $\mathcal{A}$ . The complexity of the algorithm, measured by the number of arithmetic operations in $\mathrm{D}$ is bounded by $\left( \sum_{i=1}^{m} D^{O ( \log^{2} ( k ) )}_{i} +1 \right) ( k^{\log ( k )} d )^{O ( k\log^{2} ( k ))}$ , where $d= \mathrm{deg} ( P )$ , and $D_{i}$ is the degree of the real univariate representation describing the point $p_{i}$ . The best previous algorithm for this problem had complexity $\mathrm{card} ( \mathcal{A} )^{O ( 1 )} d^{O ( k^{3/2} )}$ due to Basu, Roy, Safey-El-Din, and Schost (2012), where it is assumed that the degrees of the polynomials appearing in the representations of the points in $\mathcal{A}$ are bounded by $d^{O ( k )}$ . As an application of our result we prove that for any real algebraic subset $V$ of $\mathbb{R}^{k}$ defined by a polynomial of degree $d$ , any connected component $C$ of $V$ contained in the unit ball, and any two points of $C$ , there exist a semi-algebraic path connecting them in $C$ , of length at most $( k ^{\log (k )} d )^{O ( k\log ( k ) )}$ , consisting of at most $( k ^{\log (k )} d )^{O ( k\log ( k ) )}$ curve segments of degrees bounded by $( k ^{\log ( k )} d )^{O ( k \log ( k) )}$ . While it was known previously, by a result of D'Acunto and Kurdyka, that there always exists a path of length $( O ( d ) )^{k-1}$ connecting two such points, there was no upper bound on the complexity of such a path.

preprint2013arXiv

Zero-nonzero and real-nonreal sign determination

We consider first the zero-nonzero determination problem, which consists in determining the list of zero-nonzero conditions realized by a finite list of polynomials on a finite set Z included in C^k with C an algebraic closed field. We describe an algorithm to solve the zero-nonzero determination problem and we perform its bit complexity analysis. This algorithm, which is in many ways an adaptation of the methods used to solve the more classical sign determination problem, presents also new ideas which can be used to improve sign determination. Then, we consider the real-nonreal sign determination problem, which deals with both the sign determination and the zero-nonzero determination problem. We describe an algorithm to solve the real-nonreal sign determination problem, we perform its bit complexity analysis and we discuss this problem in a parametric context.

preprint2009arXiv

Bounding the radii of balls meeting every connected component of semi-algebraic sets

We prove explicit bounds on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semi-algebraic set $S \subset \mathbbm{R}^k$ defined by a quantifier-free formula involving $s$ polynomials in $\mathbbm{Z}[X_1, ..., X_k]$ having degrees at most $d$ , and whose coefficients have bitsizes at most $τ$ . Our bound is an explicit function of $s, d, k$ and $τ$ , and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of $S$ (including the unbounded components). While asymptotic bounds of the form $2^{τd^{O (k)}}$ on these quantities were known before, some applications require bounds which are explicit and which hold for all values of $s, d, k$ and $τ$ . The bounds proved in this paper are of this nature.

preprint2008arXiv

Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials

Let $\R$ be a real closed field, ${\mathcal Q} \subset \R[Y_1,...,Y_\ell,X_1,...,X_k],$ with $ °_{Y}(Q) \leq 2, °_{X}(Q) \leq d, Q \in {\mathcal Q}, #({\mathcal Q})=m,$ and ${\mathcal P} \subset \R[X_1,...,X_k]$ with $°_{X}(P) \leq d, P \in {\mathcal P}, #({\mathcal P})=s$, and $S \subset \R^{\ell+k}$ a semi-algebraic set defined by a Boolean formula without negations, with atoms $P=0, P \geq 0, P \leq 0, P \in {\mathcal P} \cup {\mathcal Q}$ . We prove that the sum of the Betti numbers of $S$ is bounded by $\ell^2 (O(s+\ell+m)\ell d)^{k+2m}.$ This is a common generalization of previous results on bounding the Betti numbers of closed semi-algebraic sets defined by polynomials of degree $d$ and 2, respectively. We also describe an algorithm for computing the Euler-Poincaré characteristic of such sets, generalizing similar algorithms known before. The complexity of the algorithm is bounded by $(\ell s m d)^{O(m(m+k))}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.