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)$?

1 Answers 1

1

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.

  • 0
    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.2011-03-09