Welcome to MathOverflow

Question

3

1

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.

edited Aug 11 2011 at 18:28

Boris Bukh
3,032●9●26

asked Aug 11 2011 at 14:28

Al Tal
195●5

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

muestrass · Answer 1 · 2011-08-11 16:05:41Z UTC

1

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.

answered Aug 11 2011 at 16:05

muestrass
33●3

	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

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)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.