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.

Improve this question
$\endgroup$
4
  • $\begingroup$ How large is $n$ typically in your problem? $\endgroup$
    – Moritz Firsching
    Aug 5, 2015 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$
    – TDH
    Aug 5, 2015 at 12:55
  • $\begingroup$ Check out the edit to my answer. $\endgroup$
    – Igor Rivin
    Aug 5, 2015 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$
    – TDH
    Aug 5, 2015 at 14:08

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
3
  • $\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$
    – TDH
    Aug 5, 2015 at 13:04
  • $\begingroup$ @SDG that was not easy to guess. $\endgroup$
    – Igor Rivin
    Aug 5, 2015 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$
    – TDH
    Aug 5, 2015 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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