Source author record

Marie-Françoise 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 math.GT Symbolic Computation

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A new general formula for the Cauchy Index on an interval with Subresultants

We present a new formula for the Cauchy index of a rational function on an interval using subresultant polynomials. There is no condition on the endpoints of the interval and the formula also involves in some cases less subresultant polynomials.

preprint2014arXiv

A baby step-giant step roadmap algorithm for general algebraic sets

Let $\mathrm{R}$ be a real closed field and $\mathrm{D} \subset \mathrm{R}$ an ordered domain. We give an algorithm that takes as input a polynomial $Q \in \mathrm{D}[X_1,\ldots,X_k]$ , and computes a description of a roadmap of the set of zeros, $\mathrm{Zer}(Q,\mathrm{R}^k)$ , of $Q$ in $\mathrm{R}^k$ . The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain $\mathrm{D}$ , is bounded by $d^{O(k \sqrt{k})}$ , where $d = \mathrm{deg}(Q)\ge 2$ . As a consequence, there exist algorithms for computing the number of semi-algebraically connected components of a real algebraic set, $\mathrm{Zer}(Q,\mathrm{R}^k)$ , whose complexity is also bounded by $d^{O(k \sqrt{k})}$ , where $d = \mathrm{deg}(Q)\ge 2$ . The best previously known algorithm for constructing a roadmap of a real algebraic subset of $\mathrm{R}^k$ defined by a polynomial of degree $d$ has complexity $d^{O(k^2)}$ .

preprint2008arXiv

Computing the Betti numbers 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$. Let $S \subset \R^{\ell+k}$ be 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 describe an algorithm for computing the the Betti numbers of $S$ . The complexity of the algorithm is bounded by $(\ell s m d)^{2^{O(m+k)}}$ . The complexity of the algorithm interpolates between the doubly exponential time bounds for the known algorithms in the general case, and the polynomial complexity in case of semi-algebraic sets defined by few quadratic inequalities known previously. Moreover, for fixed $m$ and $k$ this algorithm has polynomial time complexity in the remaining parameters.

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.