Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Let $f_1,...,f_n$ be a set of polynomials in $x_1,...,x_n$ with rational coefficients. I need to check whether a system $$f_1=a_1,...,f_n=a_n$$ has a real solution for large enough count of points.

To specify, there is 4 polynomials of degree 2 in 4 variables, and 10^4-10^7 values of $a_1,...,a_n$. I tried

Size = 30 (* really 100-300 *)
f[x1_, x2_, y1_, y2_] := x1 + y1 - 1 (* in fact I need polynomial of degree 2, *)
g[x1_, x2_, y1_, y2_] := x2 + y2     (* but it does not work even for degree 1 *)
Equation[a_, b_] := Reduce[f[x1, x2, y1, y2] == 0 && g[x1, x2, y1, y2] == 0 && 
    x1^2 + x2^2 == a && y1^2 + y2^2 == b, {x1, x2, y1, y2}, Reals]
CheckPoint[{a_, b_}] := ! (FindInstance[Equation[a, b], {x1, x2, y1, y2}, Reals] == {})
Points = Select[Tuples[Range[-Size, Size], 2], CheckPoint]
Graphics[Point[#] & /@ Points, Frame -> True, 
    PlotRange -> {{-Size, Size}, {-Size, Size}}]

but it reduces system each time. Is there efficient enough way to do it almost in no time?

share|improve this question
    
Could you send some code? –  Mahdi Jun 6 at 18:40
    
most likely you need to tackle this numerically ( FindRoot ) –  george2079 Jun 6 at 19:50

1 Answer 1

Solutions in this example will all have x1 = (1+a-b)/2. You can use that to solve for x2:

Solve[((1 + a - b)/2)^2 + x2^2 == a^2, x2]

(* Out[46]= {{x2 -> -(1/2) Sqrt[-1 - 2 a + 3 a^2 + 2 b + 2 a b - 
     b^2]}, {x2 -> 1/2 Sqrt[-1 - 2 a + 3 a^2 + 2 b + 2 a b - b^2]}} *)

So the condition that there be real-valued solutions is that 1 - 2 a + 3 a^2 + 2 b + 2 a b - b^2>=0. You can check that instead of invoking FindInstance on the full system and it will be much faster.

share|improve this answer
    
"in fact I need polynomial of degree 2" –  se0808 Jun 9 at 5:39
    
I can only work with the input I am provided. Feel free to post the actual problem of interest. –  Daniel Lichtblau Jun 9 at 15:36
    
Thank you, Daniel, I mean only that the question is more general, whether there is a way to find out solvability of arbitrary polynomial system over reals, not considering any concrete input. –  se0808 Jun 9 at 15:51
    
The answer is yes, clearly, and you are doing so in a way that is possibly optimal, lacking any information about the specifics of the system. That said, there may be cases where some a priori analysis can be done. Your examples, both the one posted and the one you actually want to tackle, probably both fall into this category. Reason being, most things stay the same between systems, only certain parameters get altered. In such cases there are sometimes preprocessing approaches that can improve speed for e.g. questions of existence of real solutions. –  Daniel Lichtblau Jun 9 at 16:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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