Algorithm for reversion of power series?

785 Views Asked by At

Given a function $f(x)$ of the form:

$$f(x) = x/(a_0x^0+a_1x^1+a_2x^2+a_3x^3+a_4x^4+a_5x^5+...a_nx^n)$$

Let $A$ be an arbitrary (any) infinite lower triangular matrix with ones in the diagonal:

$$A = \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{array}\right)$$

Downshift the entries in matrix $A$ one row and call it $X$:

$$X=\left(\begin{array}{cccc} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \end{array} \right)$$

Calculate matrix powers of $X$: $X^0,X^1,X^2,X^3,X^4,X^5,...,X^n$

Then replace the entries in matrix $A$ with:

$$A=a_0X^0+a_1X^1+a_2X^2+a_3X^3+...+a_nX^n$$

Repeat process until the first column in $A$ has converged.

Is it then true that the entries in the first column of $A$ will be the coefficients in the power series for the reverse function of $f(x)$?

Calculations suggests it is.

http://pastebin.com/fsCtBUe1

https://oeis.org/transforms.html

Mathematica:

(*program start*)
(*coefficients (coeff) in power series can be changed*)
Clear[t, n, k, i, nn, x];
coeff = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  1}; mp[m_, e_] := 
 If[e == 0, IdentityMatrix@Length@m, MatrixPower[m, e]]; nn = 
 Length[coeff]; cc = Range[nn]*0 + 1; Monitor[
 Do[Clear[t]; t[n_, 1] := t[n, 1] = cc[[n]];
  t[n_, k_] := 
   t[n, k] = 
    If[n >= k, 
     Sum[t[n - i, k - 1], {i, 1, 2 - 1}] - 
      0*Sum[t[n - i, k], {i, 1, k - 1}], 0];
  A4 = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
  A5 = A4[[1 ;; nn - 1]]; A5 = Prepend[A5, ConstantArray[0, nn]];
  cc = Total[
    Table[coeff[[n]]*mp[A5, n - 1][[All, 1]], {n, 1, nn}]];, {i, 1, 
   nn}], i]; cc
(*Mats Granvik,Jul 11 2015*)
(*program end*)