2
$\begingroup$

I have an algebra that behaves very similarly to polynomials. A frequent occurrence there is multivariate polynomials on the form $\prod_i(x_i+y_i) - \prod_i x_i$. In this algebra subtraction is prohibitively expensive.

Are there any good algorithms for efficient computation of this kind of polynomial?

$\endgroup$
1
$\begingroup$

Define $P_i=(x_1+y_1)\dots(x_i+y_i)x_{i+1}\dots x_n$ for $0\leq i \leq n$, so we want to compute $$P_n-P_0 = (P_n-P_{n-1}) + (P_{n-1} - P_{n-2}) + \dots + (P_1 - P_0).$$

which can be computed as a sum of the differences $$P_i-P_{i-1}=(x_1+y_1)\dots(x_{i-1}+y_{i-1})y_ix_{i+1}\dots x_n.$$

$\endgroup$
  • $\begingroup$ Wouldn't this miss the term $x_1*(x_2+y_2)*x_3$ for example? $\endgroup$ – Bomaz Sep 11 '17 at 13:24
  • $\begingroup$ @Bomaz: $x_1(x_2+y_2)x_3$ includes the monomial $x_1x_2x_3$, which does not appear in your original polynomial $\endgroup$ – Dap Sep 11 '17 at 15:19

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.