1
$\begingroup$

I need to calculate particular coefficients of the composition of two power series in non-commutative variables. The code below which works fine truncates power series in degree $n=5$. For $n=6$ (the definition of $F$ being modified correspondingly) it runs out of memory. Is there any trick I can use to make it work for $n=6$?

ClearAll[ExpandNCM, F, x, y, z]
n := 5;
ExpandNCM[a___] := 0 /; Head[a] == NonCommutativeMultiply && Length[a] > n;
ExpandNCM[(h : 
NonCommutativeMultiply)[a___, b_Plus, 
  c___]] := Distribute[h[a, b, c], Plus, h, Plus, ExpandNCM[h[##]]\&];
ExpandNCM[(h : 
NonCommutativeMultiply)[c1___,
     b_Times, c2___]] := Most[b] ExpandNCM[h[c1, Last[b], c2]];
ExpandNCM[a_ + b_] := ExpandNCM[a] + ExpandNCM[b];
ExpandNCM[a_ b_] := a ExpandNCM[b];
ExpandNCM[a_] := ExpandAll[a];

F[x_, y_] := x + y + r01 x ** y + r10 y ** x + s001 x ** x ** y + s010 x ** y ** x +
  s100 y ** x ** x + s011 x ** y ** y + s101 y ** x ** y + s110 y ** y ** x + 
  t0001 x ** x ** x ** y + t0010 x ** x ** y ** 
  x + t0100 x ** y ** x ** x + t1000 y ** x ** x ** x +
  t0011 x ** x ** y ** y + t0110 x ** y ** y ** x + 
  t1100 y ** y ** x ** x + t1010 y ** x ** y ** x + 
  t0101 x ** y ** x ** y + t1001 y ** x ** x ** y + 
  t1110 y ** y ** y ** x + t1101 y ** y ** x ** y + 
  t1011 y ** x ** y ** y + t0111 x ** y ** y ** y + u00001 x ** x ** 
  x ** x ** y + u00010 x ** x ** x ** y ** x + u00011 x ** x ** x ** y ** 
      y + u00100 x ** x ** y ** 
  x ** x + u00101 x ** x ** y ** x ** y + u00110 x ** 
  x ** y ** y ** x + u00111 x ** x ** y ** y ** y + 
  u01000 x ** y ** x ** x ** x + u01001 x ** y ** 
  x ** x ** y + u01010 x ** y ** x ** y ** x + u01011 
  x ** y ** x ** y ** y + u01100 x ** y ** y ** x ** 
  x + u01101 x ** y ** y ** x ** y + u01110 x ** 
  y ** y ** y ** x + 
u01111 x ** y ** y ** y ** y + 
  u10000 y ** x ** x ** x ** x + u10001 y ** x ** x ** x ** y + u10010 
      y ** x ** x **
   y ** x + u10011 y ** x ** x ** y ** y + u10100 y ** x ** y **
   x ** x + u10101 y ** x ** y ** x ** y + u10110 y ** x ** y **
   y ** x + u10111 y ** x ** y ** y ** y + u11000 y ** y ** x **
   x ** x + u11001 y ** y ** x ** x ** y + u11010 y ** y ** x **
   y ** x + u11011 y ** y ** x ** y ** y + u11100 y ** y ** y **
   x ** x + u11101 y ** y ** y ** x ** y + u11110 y ** y ** y ** y ** x;

Coefficient[ExpandNCM[F[F[x, y], z]], z ** y ** y ** x ** y]
$\endgroup$
  • $\begingroup$ Is it safe to assume from the last line of your code that you're only interested in a specific coefficient of the composition? If that's the case, take a look at this answer which allows you to circumvent expanding the series. $\endgroup$ – IPoiler Nov 5 '15 at 16:47
  • $\begingroup$ @ IPoiler Thanks for your comment and link. Actually, I need all the coefficients. The code runs out of memory even if I calculate a single coefficient. $\endgroup$ – 8k14 Nov 5 '15 at 16:57
  • $\begingroup$ Hmm, it' s surprising then that the expansion runs into issues here since it' s not a particularly deep composition, regardless of truncated degree. I suspect that applying something similar to the linked solution in an iterative fashion over all words/terms, rather than expanding, should tie up less intermediate memory though. $\endgroup$ – IPoiler Nov 5 '15 at 17:38
  • $\begingroup$ @IPoiler Thank you. Could you please be a bit more specific. $\endgroup$ – 8k14 Nov 5 '15 at 17:57
  • 1
    $\begingroup$ To use Coefficient in this context requires expanding the expression fully, as you've shown with the need for a modified version of the documentation's ExpandNCM example. D.L.'s coeff function is able to get around having to expand, which is what's causing you to run out of memory at higher degrees. By generating the list of terms you're looking for coefficients of, then doing something like coeff[F[F[x,y]z],#,{x,y,z}]/@lisOfTerms, you can get the coefficients without ExpandNCM going full cookie monster on your memory. $\endgroup$ – IPoiler Nov 5 '15 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.