1
$\begingroup$

I have a number of long symbolic polynomial expressions of the form $$ p_n(x_1, \ldots x_r) = a_{1,n}(x) + a_{2,n}(x) + \ldots a_{m,n}(x), $$ where $a_{m,n}(x)$ is some monomial. Ultimately, I want to construct the product $$ p_1 p_2 p_3 p_4, $$ to which a function $f$ is applied to each monomial. That is, if
$$ p_1 p_2 p_3 p_4 = b_1(x) + b_2(x) + \ldots, $$ where $b_m(x)$ is a monomial, I want $$ f(b_1(x)) + f(b_2(x)) + \ldots $$

Schematically, my code currently looks like

  1. Expand the product.
  2. Apply $f$ to each term in the resultant sum.

This works well for small expressions, but is quite slow when the total number of terms in the product is greater than $10^7$ (due to the symbolic nature of the code). Any advice for improving speed / memory performance would be appreciated.

As an example, consider the code:

p1 = 8x[1]^2 + 63y[1]^2 + 4z[1]^2;
p2 = 4x[2]^2 + 5y[2]^2 + 98z[2]^2;
p3 = 2x[3]^2 + 5y[3]^2 + 32z[3]^2;
p4 = 4x[4]^2 + 9y[4]^2 + 3z[4]^2;

exp = Expand[p1 p2 p3 p4];
answer = Map[f, exp];
$\endgroup$
  • 1
    $\begingroup$ Can you give a minimal example, using Mathematica code that one can use to start with? $\endgroup$ – Nasser Feb 1 '17 at 4:55
  • $\begingroup$ Edited to add an example. $\endgroup$ – Ultima Feb 1 '17 at 5:06
  • 3
    $\begingroup$ If the Expand is the bottleneck then I do not have any good ideas. If it is the Map, that can be made faster by changing the sum to a list, mapping, and changing back. Compare: AbsoluteTiming[exp = Expand[p1^4*p2^8*p3^12* p4^12];]In[28]:= AbsoluteTiming[answer1 = Map[f, exp];] AbsoluteTiming[answer2 = Apply[Plus, Map[f, Apply[List, exp]]];] answer1 === answer2 Out[28]= {9.68927, Null} Out[29]= {5.161995, Null} Out[30]= True $\endgroup$ – Daniel Lichtblau Feb 1 '17 at 5:13
  • $\begingroup$ Unfortunately Expand is the bottleneck. $\endgroup$ – Ultima Feb 1 '17 at 5:14
2
$\begingroup$

It seems, although I'm not sure about the generality, that expanding piece by piece improves the timing that Expand needs.

p1 = 8 x[1]^2 + 63 y[1]^2 + 4 z[1]^2;
p2 = 4 x[2]^2 + 5 y[2]^2 + 98 z[2]^2;
p3 = 2 x[3]^2 + 5 y[3]^2 + 32 z[3]^2;
p4 = 4 x[4]^2 + 9 y[4]^2 + 3 z[4]^2;

and now compare:

AbsoluteTiming[e1 = Expand[p1^4*p2^8*p3^12*p4^12];]
AbsoluteTiming[e2 = Fold[Expand[#1*#2] &, {p1^4, p2^8, p3^12, p4^12}];]
e1 === e2
(* {15.3403, Null} *)
(* {9.41921, Null} *)
(* True *)

It takes only about 60% of the time. Not blazingly faster, but something.

$\endgroup$
  • $\begingroup$ As you mention, I'm not sure if this comparison is valid in the general case. Using your code, for large polynomials expanding piece by piece seems to be slightly slower. $\endgroup$ – Ultima Feb 1 '17 at 8:56
  • $\begingroup$ Maybe you can investigate further and take my suggestion only as a hint that it is indeed possible to influence the runtime by reordering the chain of evaluation. $\endgroup$ – halirutan Feb 1 '17 at 9:02

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.