1
$\begingroup$

I have 2 polynomials $p_1(x_1,\ldots,x_n)$ and $p_2(x_1,\ldots,x_n)$, of which I have to compute the product, with a special property: The exponent of each variable is always either $0$ or $1$, where every exponent greater than $1$ gets cut down to $1$. E.g. $x_1 * x_1x_2 = x_1x_2$, and the result of $(2x_1x_2x_4 + 4x_2x_3) * (3x_2x_3 - x_1x_4)$ would be $2x_1x_2x_3x_4 -2x_1x_2x_4 +12x_2x_3$. Additionally, values for all but one variables are given. So the result would be some polynomial $p(x_k) = ax_k + b$.

Currently I compute the product the usual way, multiplying each summand of $p_1$ with every summand in $p_2$, and then apply the values for all known $x_i$. But since both polynomials easily contain $10^5$ summands each, the algorithm iterates over $10^{10}$ elements, which simply takes too much time.

My question is: Does there exists a more effective procedure to compute $p(x_k)$?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Well first of all, if you're making the substitution $x_i^2 = x_i$ for all $i$, then it had better be the case that the only values you are interested in (and so are substituting in) are $x_i = 0$ and $x_i=1$, since these are the only solutions to this equation. So what you're saying is that you're interested in the value of the product $p_1p_2$ as a function of $x_k\in\{0,1\}$ when values in $\{0,1\}$ are substituted in for all the other variables. So just compute $p_1$ and $p_2$ with the given values for indices $i\neq k$ and both values of $x_k$. Multiply the resulting values for the two polynomials when $x_k = 0$ to get the value $p(0)$ and multiply the values for the two polynomials when $x_k =1$ to get the value $p(1)$. Then $b = p(0)$ and $a = p(1) - p(0)$. This will reduce your work from evaluating $10^{10}$ terms to evaluating $4\times 10^5$ terms.

$\endgroup$
3
  • $\begingroup$ For the resulting polynomial only the values in $\{0,1\}$ matter. But for the steps in between (for which I need to calculate the product) they are not. Therefore the resulting polynomial must not be equal to the result of the 'native' product, hence values for variables are not bounded to be in $\{0, 1\}$. To explain the usage: this is used for an interactive protocol for QBF. $\endgroup$
    – Mike B.
    Commented Mar 7, 2011 at 12:03
  • $\begingroup$ @Mike B.: I still don't understand why you can't substitute in the values of the variables to evaluate $p_1$ and $p_2$ and multiply the values of these to get the values of $p$ and then compute $a$ and $b$ as I described. It seems like this is the natural thing to do, so could you add some more explanation as to why this is not what you want? Perhaps the fact that you are enforcing $x_i^2 = x_i$ at some times and not other times means that what you want in some sense "looks like" polynomial multiplication but mathematically it really isn't? $\endgroup$
    – Noah Stein
    Commented Mar 7, 2011 at 16:06
  • $\begingroup$ The reason why I cannot substitute the values of the variables in $p_1$ and $p_2$ is the following: Assume $p_1(x_1,x_2) = x_1 + x_2$, and $p_2(x_1,x_2) = x_1 - x_2$, as well as $x_1 = 5$. If I substitute $x_1$ before the calculation, I get $25 - x_2$, whereas the solution I need would be $5 - x_2$, as the result without the substitution is supposed to be $x_1 - x_2$ (since $p_1(x_1,x_2) * p_2(x_1,x_2) = x_1^2 - x_2^2$, and exponents greater $1$ get set to $1$). It isn't a usual polynomial multiplication, but besides the exponents getting bound to $\{0,1\}$ it is the same. $\endgroup$
    – Mike B.
    Commented Mar 9, 2011 at 8:05

You must log in to answer this question.

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