## Quick algorithm for finding real solutions for a system polynomial equations

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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
How dense are your polynomials? – Igor Rivin Aug 11 2011 at 15:29
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?) – Igor Rivin Aug 11 2011 at 15:38
Take a look at the implementation of Tarski-Seidenberg Theorem explained at xorshammer.com/2009/05/14/… I do not know whether this particular implementation is efficient, but it seems worth trying (easy to install, ...). – boumol Aug 11 2011 at 16:43

1
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. – Boris Bukh Aug 11 2011 at 18:32
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. – Igor Rivin Aug 11 2011 at 21:47
show 1 more comment

## 1 Answer

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.

-

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. – Andrew Aug 11 2011 at 18:03
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? – Al Tal Aug 12 2011 at 19:52
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 3, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9385828375816345, "perplexity_flag": "middle"}