3
$\begingroup$

I'm working on a project that involves solving systems of multivariate polynomial equations over the reals (and find their real solutions). Assuming that a system has a finite number of complex solutions, the two primary methods I've found for this task involve Gröbner bases (computed using Buchberger's algorithm) and Cylindrical Algebraic Decomposition (CAD). For the actual computation, we plan to use Mathematica, but I was hoping to learn about the following theoretical questions (ignoring complexity or computing logistics):

  1. Given an arbitrary polynomial system over the reals, can one use Gröbner bases/CAD to find all real solutions (in theory)? If not, are there certain constraints over the system that one can place to guarantee returning all real solutions?

  2. Could using either method ever produce a "false positive" (returning something that isn't a solution)? If this is clear given the descriptions of each method, some intuition as to why may be helpful.

  3. Where can I find literature or course materials by which I can answer the above?

Thank you for reading and for your help.

$\endgroup$
5
  • $\begingroup$ There is already a constraint for finding all real solutions of $f(x)=0$ for a polynomial $f$ in only one variable. If the degree of $f$ is $\ge 5$, then there is no formula in general for the roots. $\endgroup$ Commented Apr 8, 2021 at 15:28
  • 1
    $\begingroup$ @DietrichBurde One-variable polynomials are generally looked upon as a black box. In other words, the solution is expressed in terms of algebraic numbers together for the bounding boxes which localize the specific conjugate you need. No radicals need be harmed. $\endgroup$
    – Igor Rivin
    Commented Apr 8, 2021 at 16:23
  • $\begingroup$ @IgorRivin Yes, I know. Just wanted to remember this. $\endgroup$ Commented Apr 8, 2021 at 16:32
  • $\begingroup$ Do you agree with my edits? $\endgroup$ Commented Apr 8, 2021 at 22:20
  • $\begingroup$ You may want to take a look at Sturm & Tiwari's Verification and Synthesis Using Real Quantifier Elimination [PDF], which contains some potentially interesting comments on performance. $\endgroup$ Commented Apr 8, 2021 at 22:24

1 Answer 1

2
$\begingroup$

The standard reference is

Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise, Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics. 10. Berlin: Springer. viii, 602 p. (2003). ZBL1031.14028.

No, you can't find false positives, and yes, in theory one can find all the solution. In practice it is often very slow.

$\endgroup$

You must log in to answer this question.

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