Accessibility setting

Section: New Results

Solving Polynomial Systems over the Reals and Applications

Exact algorithms for polynomial optimization

Let $f,f_1,...,f_s$ be $n$-variate polynomials with rational coefficients of maximum degree $D$ and let $V$ be the set of common complex solutions of $𝐅=(f_1,...,f_s)$. In [7] , we give an algorithm which, up to some regularity assumptions on $𝐅$, computes an exact representation of the global infimum $f^{☆}$ of the restriction of the map $x\to f\left(x\right)$ to $V\cap {ℝ}^n$, i.e. a univariate polynomial vanishing at $f^{☆}$ and an isolating interval for $f^{☆}$. Furthermore, it decides whether $f^{☆}$ is reached and if so, it returns $x^{☆}\in V\cap {ℝ}^n$ such that $f\left(x^{☆}\right)=f^{☆}$.

This algorithm is probabilistic. It makes use of the notion of polar varieties. Its complexity is essentially cubic in ${\left(sD\right)}^n$ and linear in the complexity of evaluating the input. This fits within the best known deterministic complexity class $D^{O\left(n\right)}$.

We report on some practical experiments of a first implementation that is available as a Maple package. It appears that it can tackle global optimization problems that were unreachable by previous exact algorithms and can manage instances that are hard to solve with purely numeric techniques. As far as we know, even under the extra genericity assumptions on the input, it is the first probabilistic algorithm that combines practical efficiency with good control of complexity for this problem.

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 ${\left(sd\right)}^{O\left(n\right)}$ arithmetic operations, where $n$ and $s$ are the numbers of variables and constraints and $d$ is the maximal degree of the polynomials involved.

Subject to certain conditions, we associate in [2] to each of these problems an intrinsic system degree which becomes in worst case of order ${\left(nd\right)}^{O\left(n\right)}$ and which measures the intrinsic complexity of the task under consideration.

We design non-uniform deterministic or uniform probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems.

Algorithms for answering connectivity queries

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

In [36] , we provide a probabilistic algorithm which computes roadmaps for smooth and bounded real algebraic sets such that the output size and the running time are polynomial in ${\left(nD\right)}^{nlog\left(n\right)}$. More precisely, the running time of the algorithm is essentially subquadratic in the output size. Even under these extra assumptions, it is the first roadmap algorithm with output size and running time polynomial in ${\left(nD\right)}^{nlog\left(n\right)}$.

Nearly Optimal Refinement of Real Roots of a Univariate Polynomial

In [33] , we consider the following problem. We assume that a real square-free polynomial $A$ has a degree $d$, a maximum coefficient bitsize $\tau$ and a real root lying in an isolating interval and having no nonreal roots nearby (we quantify this assumption). Then we combine the Double Exponential Sieve algorithm (also called the Bisection of the Exponents), the bisection, and Newton iteration to decrease the width of this inclusion interval by a factor of $t=2^L$. The algorithm has Boolean complexity $O(d^2\tau +dL)$. This substantially decreases the known bound $O(d^3+d^{2}L)$. Furthermore we readily extend our algorithm to support the same complexity bound for the refinement of $r$ real roots, for any $r\le d$, by incorporating the known efficient algorithms for multipoint polynomial evaluation. The main ingredient for the latter ones is an efficient algorithm for (approximate) polynomial division; we present a variation based on structured matrices computation with quasi-optimal Boolean complexity.

Accelerated Approximation of the Complex Roots of a Univariate Polynomial

Highly efficient and even nearly optimal algorithms have been developed for the classical problem of univariate polynomial root-finding, but this is still an area of active research. By combining some powerful techniques developed in this area we devise in [20] new nearly optimal algorithms, whose substantial merit is their simplicity, important for the implementation.

Nearly Optimal Computations with Structured Matrices

In [21] , we estimate the Boolean complexity of multiplication of structured matrices by a vector and the solution of nonsingular linear systems of equations with these matrices. We study four basic most popular classes, that is, Toeplitz, Hankel, Cauchy and Vandermonde matrices, for which the cited computational problems are equivalent to the task of polynomial multiplication and division and polynomial and rational multipoint evaluation and interpolation. The Boolean cost estimates for the latter problems have been obtained by Kirrinnis, except for rational interpolation, which we provide now. All known Boolean cost estimates for these problems rely on using Kronecker product. This implies the d-fold precision increase for the d-th degree output, but we avoid such an increase by relying on distinct techniques based on employing FFT. Furthermore we simplify the analysis and make it more transparent by combining the representation of our tasks and algorithms in terms of both structured matrices and polynomials and rational functions. This also enables further extensions of our estimates to cover Trummer's important problem and computations with the popular classes of structured matrices that generalize the four cited basic matrix classes.

Bounds for the Condition Number for Polynomials with Integer Coefficients

In [31] , we consider the problem of bounding the condition number of the roots of univariate polynomials and polynomial systems, when the input polynomials have integer coefficients. We also introduce an aggregate version of the condition numbers and we prove bounds of the same order of magnitude as in the case of the condition number of a single root.