4
$\begingroup$

I am trying to solve the following over determined system of polynomials

\begin{align} & p_1(x_1,x_2,\ldots,x_n)=0, \\ & p_2(x_1,x_2,\ldots,x_n)=0, \\ & \vdots \\ & p_m(x_1,x_2, \ldots, x_n)=0, \\ & (x_1-l_1) (x_1-(l_1+1)) (x_1 - (l_1 + 2))\cdots (x_1-(u_1-1))(x_1-u_1)=0, \\ & \vdots \\ & (x_n-l_n) (x_n-(l_n+1)) (x_n - (l_n + 2))\cdots (x_n-(u_n-1))(x_n-u_n)=0 \cdots (x_n-u_n)=0. \end{align}

Here $l_1,u_1, \ldots, l_n, u_n$ are non-negative integers. The last $n$ equations mean that $x_i \in \{l_i, l_i +1, l_i+2, \ldots, u_i-1, u_i\}$ for all $i \in \{1,\ldots, n\}$. I know that we can use Groebner bases to solve the polynomial system.

But is there a better way to solve such over-determined polynomial system? I will appreciate any suggestion or direction.

$\endgroup$
  • $\begingroup$ How large is $n$ typically in your problem? $\endgroup$ – Moritz Firsching Aug 5 '15 at 5:46
  • $\begingroup$ In my problem $n$ is the difference between the number of edges and nodes of a directed graph. For now I am taking $n \leq 50$. $\endgroup$ – SDG Aug 5 '15 at 12:55
  • $\begingroup$ Check out the edit to my answer. $\endgroup$ – Igor Rivin Aug 5 '15 at 13:45
  • $\begingroup$ Thanks a lot for your answer, I will check it. It seems that constraint programming too might be a good alternative. $\endgroup$ – SDG Aug 5 '15 at 14:08
3
$\begingroup$

I am not sure I understand what the ellipsis $\dots$ means in the last set of equations, since it seems that you only have pairs $l_i, u_i.$ If that is true, that means that there are $2^n$ possible values for the $n$-tuple $x_1, \dotsc, x_n,$ and substituting each possible $n$-tuple into your first $n$ equations, and checking will take time roughly $O(n 2^n)$ (with small constants), which will be WAY faster than Grobner bases in practice.

EDIT The OP explains in the comment that his notation means that $x_k$ is an integer at most equal to $u_k$ and at least equal to $l_k.$ If that is the case, and $u_i - l_1 \gg 1,$ so that brute force search is prohibitively expensive, the best approach is almost certainly back-tracking search. In fact, the form of the problem is not unlike that of the $N$-queens problem (which google).

$\endgroup$
  • $\begingroup$ Thanks a lot for your response. Actually it means $x_i \in \{l_i,l_i+1,l_i+2,\ldots,u_i-1,u_i\}$, with $l_i, u_i$ being non-negative integers. $\endgroup$ – SDG Aug 5 '15 at 13:04
  • $\begingroup$ @SDG that was not easy to guess. $\endgroup$ – Igor Rivin Aug 5 '15 at 13:41
  • $\begingroup$ I agree with you. I read my original post and found it confusing myself. I have clarified the point in the original problem. Thanks again. $\endgroup$ – SDG Aug 5 '15 at 13:46

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.