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
    Commented 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
    Commented Aug 5, 2015 at 12:55
  • $\begingroup$ Check out the edit to my answer. $\endgroup$
    – Igor Rivin
    Commented 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
    Commented 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
    Commented Aug 5, 2015 at 13:04
  • $\begingroup$ @SDG that was not easy to guess. $\endgroup$
    – Igor Rivin
    Commented 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
    Commented Aug 5, 2015 at 13:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .