I'm trying to determine whether any solutions exist to a system of ( n + 1 ) polynomial equations in n unknowns. For example: x y = − 2 x 2 − 1 = 0 y 3 − 3 y 2 + 2 y = 0 This is an accurate simplification of my actual system in that the first equation contains mixed terms with all variables represented and the remaining n equations are univariate, and that the maximum degree of any term (say, D) is in the low single digits. The actual system is very large ( n is 10 3 to 10 4 ), but with similar D. It also typically has many terms in the first equation.In this example, the system is in fact consistent ( x = − 1 ; y = 2). Were the first equation altered, however, to x y = − 3, the system would be inconsistent. My naive approach is to find the solutions to the last n equations (here x ∈ { − 1 , 1 } , y ∈ { 0 , 1 , 2 }) and try all combinations thereof until one satisfies the first equation or I exhaust the combinations, but this requires roughly D n checks, which isn't feasible for large systems. It's also not necessary to find a solution, just prove whether one exists.

Question

I&#039;m trying to determine whether any solutions exist to a system of   (  n  +  1  ) polynomial equations in   n unknowns. For example:                    x        y                            =        −        2                                      x          2                −        1                            =        0                                      y          3                −        3                  y          2                +        2        y                            =        0            This is an accurate simplification of my actual system in that the first equation contains mixed terms with all variables represented and the remaining n equations are univariate, and that the maximum degree of any term (say,   D) is in the low single digits. The actual system is very large (  n is       10    3   to       10    4  ), but with similar   D. It also typically has many terms in the first equation.In this example, the system is in fact consistent (  x  =  −  1  ;  y  =  2). Were the first equation altered, however, to   x  y  =  −  3, the system would be inconsistent. My naive approach is to find the solutions to the last n equations (here   x  ∈  {  −  1  ,  1  }  ,  y  ∈  {  0  ,  1  ,  2  }) and try all combinations thereof until one satisfies the first equation or I exhaust the combinations, but this requires roughly       D    n   checks, which isn&#039;t feasible for large systems. It&#039;s also not necessary to find a solution, just prove whether one exists.

Lydia Carey · Accepted Answer

Verifying the consistency of a polynomial equation system is fairly simple.All you have to do is calculate the grobner basis for the system. If the Grobner basis is (1), then the system is inconsistent, otherwise not. Every system of polymonial equations&#039; grobner basis can be quickly determined using Mathematica. The monomial ordering won&#039;t matter at all for consistency checks.

Jeffrey Jordon · Accepted Answer

I&#039;m not sure you can generally hope for a quick algorithm. Say the first equation has the following form.a1x1+a2x2+⋯+anxn=0where &amp;nbsp;a1,a2,…,anare positive integers, and the other n equations are all of the formS={a1,a2,…,an}&amp;nbsp;It is NP-complete (despite the fact that the Wikipedia entry claims it&#039;s a &quot;simple&quot; hard problem that&#039;s frequently resolved in practice using dynamic programming).

I'm trying to determine whether any solutions exist to a system of ( n + 1 ) polyn

Answered question

Answer & Explanation

New Questions in Algebra I