Would you please recommend a computer program that could give quick answer Yes/No for the question: does there exist a real solution of a given system of polynomial equations with integer coefficients. I will need it to solve a huge list of such systems, each of them is over $\mathbb{R}^6$, has $6$ equations of degree $4$ or less. Coefficients are also quite small. Maple's Triangularize procedure for most of the cases works too long, so applying it for big list is almost impossible.

  • 1
    $\begingroup$ How dense are your polynomials? $\endgroup$ – Igor Rivin Aug 11 '11 at 15:29
  • $\begingroup$ Also, what do the monomials look like (that is, do variables actually appear with degree 4, or is the degree of any given variable bounded by 1 or 2?) $\endgroup$ – Igor Rivin Aug 11 '11 at 15:38
  • $\begingroup$ Take a look at the implementation of Tarski-Seidenberg Theorem explained at xorshammer.com/2009/05/14/a-suite-of-cool-logic-programs I do not know whether this particular implementation is efficient, but it seems worth trying (easy to install, ...). $\endgroup$ – boumol Aug 11 '11 at 16:43
  • 1
    $\begingroup$ I asked a similar question at mathoverflow.net/questions/1493/…, have a look at the answers. QEPCAD somewhat faster than Maple/Mathematica, but less pleasant to use. If you problem allows, try solving over complex numbers, and then restrict. $\endgroup$ – Boris Bukh Aug 11 '11 at 18:32
  • $\begingroup$ If the OP's problem is "generic", then, since the number of equations equals the number of unknowns, the solution is a zero-dimensional variety, the number of complex points of which is bounded by the product of the degrees, or 4096, so the problem should not be so bad by sub-resultants. $\endgroup$ – Igor Rivin Aug 11 '11 at 21:47

Have you thought obtain a Groebner basis of the set of defining polynomials of your system? Maybe, it could simplify considerably the aspect of the system, and you would need a little time to calculate the real solutions of the system. For that, you could use the free software wxMaxima. If you don't have it, you can download in http://maxima.sourceforge.net/download.html.

I would like post this comment just as a comment and not as an answer, but I don't know how to do it.

  • $\begingroup$ Mathematica and Maple also can find Groebner basis quite effectively. In Mathematica there is also FindInstance[], which finds an instance of solution or gives an empty list if it can't find any. I don't know if it work always. May be a combination of both could help. $\endgroup$ – Andrew Aug 11 '11 at 18:03
  • $\begingroup$ I need the process to be very automatical, as there is a huge list I of systems I want to check. Dealing with each of the systems is not a hard problem, but it's a "handmade" work, I won't be able to check all the systems by hand. Most of software can compute Groebner basis, but is there a fast algorithm which can say Yes/No to real roots problem, having a Groebner basis of the ideal? $\endgroup$ – Al Tal Aug 12 '11 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.