# Improving Efficiency of Expand

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];

• Can you give a minimal example, using Mathematica code that one can use to start with? – Nasser Feb 1 '17 at 4:55
• Edited to add an example. – Ultima Feb 1 '17 at 5:06
• 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 – Daniel Lichtblau Feb 1 '17 at 5:13
• Unfortunately Expand is the bottleneck. – Ultima Feb 1 '17 at 5:14

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.

• 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. – Ultima Feb 1 '17 at 8:56
• 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. – halirutan Feb 1 '17 at 9:02