2
$\begingroup$

This is a follow-up (but self-contained) question to my previous one. There I asked about state-of-the-art methods to solve multivariate polynomials systems over non-algebraically closed fields in general.
I learned that the theory is more involved that I thought (I'm not working in algorithmic algebraic geometry, so I'm only familiar with the very basics, like Buchberger's algorithm, or the definition of the dimension of an ideal). Therefore it is necessary to ask a more specific questions that the previous, general one, which is more tailored to my needs.

My setup is the following:

Regarding complexity: I'm interested in solving a large number of polynomial systems (on commodity hardware), on the order of $10^4$. But each of the systems is of relatively small size - my baseline consists of least 6 different variable and 4 equations. If I could tackle this, I'd already be happy. Going further, I don't expect the systems to grow beyond about 20 different variables and 20 equations.
So perhaps I don't actually need the fastest possible algorithm and can make do with simpler, older ones - but I will let you be the judge of that.

Regarding the polynomials: There are no restrictions their coefficients, so, depending on the field I'm working in they can take any number.

Regarding the field: Regarding the field I'm working in, my baseline is $\mathbb{R}$, but I'd also be interested in $\mathbb{Q}$ and $\mathbb{Z}$. If there are methods that are much easier for one field than another, than I will the choice of the field to study be influence by the time I need to invest to learn that method, i.e. the easiest one wins.

Regardin the dimension of the ideal spanned by the polynomials: The ideal has dimension $2$ or $3$ over the complex numbers, in most cases I tested so far with the help of CAS.

What I'm looking for: I'm interested is learning about methods (I'm happy with specific references) that tell me

1) whether the system has a solution at all or not. Working over, e.g., $\mathbb{C}$, this would be easy (e.g. compute a Gröbner basis: If it contain the $1$, if and only if the solution variety is empty). But this doesn't work unfortunately for non-algebraically closed fields. Given the answers from my previous question, I'm inclined to think that answer this question shouldn't be too hard (perhaps even trivial for the expert computational geometer, which I'm not unfortunately).

2) if it has an infinite number of solutions (if the variety is zero-dimensional, things are easy of course), I would like to pick out one single variable, say $n_0\in \{1,\ldots,n\}$, project the solution variety $V(f_1,\ldots,f_s)\subseteq \mathbb{ R}^n$ (supposing we work over the field $\mathbb{R}$) along this variable onto $\mathbb{R}$ to investigate whether there exists an interval $[-\alpha,\alpha]$ around $0$ which is contained in this projected set (I don't need to understand the projected set fully). That is what I menat by "rough shape" in the title.

Improve this question
$\endgroup$
12
  • $\begingroup$ Are the coefficients exact or only floating-point numbers? $\endgroup$
    – François Brunault
    Commented May 29, 2020 at 8:37
  • $\begingroup$ @FrançoisBrunault My investigation has two steps: First, experiments, where I necessarily use floating-point precision. In a second step, based on the experiments, I will want to prove some general statements, where I will allow any real-numbers as coefficients (even if these can't be simulated any more). I'm guessing there seems to be a dramatic difference in terms of the capability of the methods you have in mind between these two cases. While I, for now, would be interested mostly in the floating-point case to do the experiments, it would be good to know if there are [...] $\endgroup$
    – user43263
    Commented May 29, 2020 at 9:11
  • $\begingroup$ some fundamental issues I might miss when doing experiments, which come from floating points. Thus I would ask you to focus on floating-point, but dt mention where I need to be careful, when passing to exact real coefficients (so that I will know where any pitfalls might lie when generalizing after I have finished experimenting; perhaps; if the exact coefficient case is more difficult I could adjust my investigation accordingly). $\endgroup$
    – user43263
    Commented May 29, 2020 at 9:14
  • $\begingroup$ If the coefficients are floating point then your question is somewhat ill-posed, because polynomial equation solving is very sensitive to the input. Think of the equation $x^2=\varepsilon$ with $\varepsilon$ near 0, the answer to your question (2) changes completely. You can certainly approximate the coefficients by decimal numbers, and apply the quantifier elimination method I mentioned to get the projection as an explicit semi-algebraic set of $\mathbb{R}$. And it's possible to decide whether a semi-algebraic set is a neighbourhood of $0$. But you have no guarantee that the answer is correct $\endgroup$
    – François Brunault
    Commented May 29, 2020 at 9:20
  • $\begingroup$ @FrançoisBrunault Well, by necessity I need to use floating point, since I don't know of a different way to carry out solving the mentioned $10^4$ systems, where the coefficients discretize a high-dimensional cube (though, afterwards, when I want to prove theorems, which is the final goal, of course I will work with coefficient from $\mathbb{R}$). $\endgroup$
    – user43263
    Commented May 29, 2020 at 9:38

1 Answer 1

Reset to default
2
$\begingroup$

Just expanding my comments to this question and the previous one:

I assume that your polynomials have rational coefficients (which seem to be the case, since you mention they are floating point numbers with fixed precision, in particular they are decimals), and that you are interested in the solutions in $\mathbb{R}^n$.

The assertion that the projection of $V(f_1,\ldots,f_s) \subset \mathbb{R}^n$ to the $x_n$ variable is a neighbourhood of 0 is a first order formula over the reals, namely \begin{equation*} \exists a>0, \forall x_n \in [-a, a], \exists x_1,\ldots,x_{n-1} \in \mathbb{R}, \forall i, f_i(x_1,\ldots,x_n) = 0. \end{equation*} It is a formula with no free variable, hence is decidable, and CAD softwares like Qepcad or Redlog will output "true" or "false".

Regarding feasibility, my worry is that the semi-algebraic set of $\mathbb{R}$ given by the projection to $x_n$ will probably involve polynomials with gigantic coefficients. You have to experiment to see whether the CAD software can still do it in reasonable time.

Regarding the theory, the heart of the algorithms is the cylindrical algebraic decoposition (CAD), and Alexandre Eremenko's answer to your previous question mentions good references. I know only the basics, but enjoyed reading the book by Bochnak, Coste and Roy. It's good to read them with a particular goal in mind and see how the corresponding algorithm works. You can also look at the documentations of the softwares I mentioned, which give a good idea of what problems they can solve.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, this really was very helpful! $\endgroup$
    – user43263
    Commented May 29, 2020 at 13:18
  • $\begingroup$ @user43263 By the way, I realize that this also works (in theory) for polynomials whose coefficients are arbitrary real numbers (which are computable to arbitrary precision, like $\pi$, $e$ or whatever...). Namely, you introduce indeterminates for these coefficients. CAD will output a boolean formula involving (in)equalities between polynomials in these indeterminates (like "$b^2-4ac \geq 0$"), and you just need to evaluate these expressions to sufficient precision to decide whether the boolean formula is true or false. $\endgroup$
    – François Brunault
    Commented May 29, 2020 at 13:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .