We consider here the problem of computing the solutions of a polynomial system
in a box . This solver uses the representation of multivariate polynomials in the Bernstein basis, analysis of sign variations and univariate solvers to localise the real roots of a polynomial system. The output is a set of smallenough boxes, which may contain these roots.
By a direct extension to the multivariate case, any polynomial of degree in the variable , can be decomposed as:
where is the tensor product Bernstein basis on the domain and are the control coefficients of on . The polynomial is represented in this basis by the order tensor of control coefficients . The size of , denoted by , is .
De Casteljau algorithm also applies in each of the direction , , so that we can split this representation in these directions. We use the following properties to isolate the roots:
Definition: For any and , let

Theorem: [Projection Lemma] For any , and any , we have

As a direct consequence, we obtain the following corollary:
Corollary: For any root of the equation in the domain , we have where

The solver implementation contains the following main steps. It consists in
As we are going to see, we have several options for each of these steps, leading to different algorithms with different behaviors, as we will see in the next sections. Indeed the solvers that we will consider are parameterized by the
equivalent to solving the system , where is an invertible matrix
As such a transformation may increase the degree of some equations, with respect to some variables, it has a cost, which might not be negligible in some cases.
Moreover, if for each polynomials of the system not all the variables are involved, that is if the systems is sparse with respect to the variables, such a preconditioner may transform it into a system which is not sparse anymore. In this case, we would prefer a partial preconditioner on a subsets of the equations sharing a subset of variables.
The following preconditioners are curently avialable:
can be considered.
This method will be particularly interesting in the cases where more than one interval have to be considered. This may happen at the beginning of the search but is less expected locally near a single root.
subdivide a domain. We will show in the next section their impact on the performance of the solver
The righthand side of this equation can be easily computed, from the sum of all the control coefficients of .
synaps/msolve/sbdslv.h
.#include <synaps/init.h> #include <synaps/mpol.h> #include <synaps/base/Seq.h> #include <synaps/msolve/sbdslv.h> typedef MPol<double> mpol_t; int main (int argc, char **argv) { using std::cout; using std::endl; mpol_t p("x0^2*x1x0*x11"), q("x0^2x1^32"); std::list<mpol_t> I; I.push_back(p); I.push_back(q); VectDse<double> dmn(4,"2 2 2 2"); // cout << solve(I, SBDSLV<double,SBDSLV_RDL>())<<endl; cout << solve(I, SBDSLV<double,SBDSLV_RDL>(1e3),dmn)<<endl; // [[1.66068,0.911523], [1.4228,0.290084] // // The result is a sequence of vectors with coefficients of double type. // The size of the vectors is the number of variables. // Here there are no solutions in the default [0,1]x[0,1] and // 2 real solutions in the box [2,2]x[2,2]). }