Section: New Results

Real Solving Polynomial Systems

In [20] , we describe an algorithm (VQE) for a variant of the real quantifier elimination problem (QE). The variant problem requires the input to satisfy a certain extra condition, and allows the output to be almost equivalent to the input. The motivation/rationale for studying such a variant QE problem is that many quantified formulas arising in applications do satisfy the extra conditions. Furthermore, in most applications, it is sufficient that the output formula is almost equivalent to the input formula. The main idea underlying the algorithm is to substitute the repeated projection step of CAD by a single projection without carrying out a parametric existential decision over the reals. We find that the algorithm can tackle important and challenging problems, such as numerical stability analysis of the widely-used MacCormack’s scheme. The problem has been practically out of reach for standard QE algorithms in spite of many attempts to tackle it. However the current implementation of VQE can solve it in about 12 hours. This paper extends the results reported at the conference ISSAC 2009.

We also focused on the interaction of real solving polynomial system with global optimization. Let $f\in \mathbb{Q}[X_1,...,X_n]$ of degree $D$. Algorithms for solving the unconstrained global optimization problem $f^{☆}={inf}_{𝐱\in {ℝ}^n}f\left(𝐱\right)$ are of first importance since this problem appears frequently in numerous applications in engineering sciences. This can be tackled by either designing appropriate quantifier elimination algorithms or by certifying lower bounds on $f^{☆}$ by means of sums of squares decompositions but there is no efficient algorithm for deciding if $f^{☆}$ is a minimum. The paper [41] is dedicated to this important problem. We design an algorithm that decides if $f^{☆}$ is reached over ${ℝ}^n$ and computes a point ${𝐱}^{☆}\in {ℝ}^n$ such that $f\left({𝐱}^{☆}\right)=f^{☆}$ if such a point exists. If $L$ is the length of a straight-line program evaluating $f$, a probabilistic version of the algorithm runs in time $\tilde{O}\left(n^2(L+n^2){\left(D{(D-1)}^{n-1}\right)}^2\right)$. Experiments show its practical efficiency.

Global optimization problems can also be tackled by computing algebraic certificates of positivity through sums of squares decompositions. Let $f_1,\cdots ,f_p$ and $f$ be polynomials in $\mathbb{Q}[X_1,\cdots ,X_n]$ and let $V=V(f_1,\cdots ,f_p)\subset {ℂ}^n$ be the algebraic variety defined by $f_1=\cdots =f_p=0$ whose dimension is denoted by $d$. Assume in the sequel that the ideal $\langle f_1,...,f_p\rangle$ is radical and equidimensional and that $V$ is smooth. In [18] , up to a generic linear change of variables, we construct families of polynomials ${𝖬}_0,...,{𝖬}_d$ in $\mathbb{Q}[X_1,...,X_n]$ such that $f\left(x\right)\ge 0$ for all $x\in V\cap {ℝ}^n$ if and only if $f$ can written as a sum of squares of polynomials in $ℝ[X_1,...,X_n]$ modulo $\langle {𝖬}_i\rangle$ for $0\le i\le d$. Such an algebraic certificate of positivity is simpler than the more general Positivstellensatz in Real Algebra. It can be used to certify lower bounds on $f^{☆}={inf}_{x\in V\cap {ℝ}^n}f\left(x\right)$. Also, computing a numerical approximation of such certificates of positivity can be reformulated as a semidefinite program which can be solved efficiently. We provide numerical experiments showing the effectiveness of our approach.

In [25] , we consider the problem of constructing roadmaps of real algebraic sets. This problem was introduced by Canny to answer connectivity questions and solve motion planning problems. Given $s$ polynomial equations with rational coefficients, of degree $D$ in $n$ variables, Canny's algorithm has a Monte Carlo cost of $s^{n}log\left(s\right)D^{O\left(n^2\right)}$ operations in $\mathbb{Q}$; a deterministic version runs in time $s^{n}log\left(s\right)D^{O\left(n^4\right)}$. A subsequent improvement was due to Basu, Pollack and Roy, with an algorithm of deterministic cost $s^{d+1}{D}^{O\left(n^2\right)}$ for the more general problem of computing roadmaps of a semi-algebraic set ($d\le n$ is the dimension of an associated object). We give a probabilistic algorithm of complexity ${\left(nD\right)}^{O\left(n^{1.5}\right)}$ for the problem of computing a roadmap of a closed and bounded hypersurface $V$ of degree $D$ in $n$ variables, with a finite number of singular points. Even under these extra assumptions, no previous algorithm featured a cost better than $D^{O\left(n^2\right)}$.