TAOCP 4.7 Exercise 11

We are asked to compute the first $N$ coefficients of the composition of two formal power series U(z) = U_0 + U_1 z + U_2 z^2 + \cdots, \qquad V(z) = V_1 z + V_2 z^2 + V_3 z^3 + \cdots,

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.7: Manipulation of Power Series

Exercise 11. ▶ [M25] (Composition of power series.) Let

$$U(z) = U_0 + U_1 z + U_2 z^2 + U_3 z^3 + \cdots \quad \text{and} \quad V(z) = V_1 z + V_2 z^2 + V_3 z^3 + \cdots$$

Design an algorithm that computes the first $N$ coefficients of $U(V(z))$.

Verified: yes
Solve time: 6m09s

Solution

We are asked to compute the first $N$ coefficients of the composition of two formal power series

$$ U(z) = U_0 + U_1 z + U_2 z^2 + \cdots, \qquad V(z) = V_1 z + V_2 z^2 + V_3 z^3 + \cdots, $$

with $V_0 = 0$, so that $U(V(z))$ is well-defined as a formal power series.

Let

$$ W(z) = U(V(z)) = W_0 + W_1 z + W_2 z^2 + \cdots. $$

We wish to compute $W_0, W_1, \dots, W_{N-1}$.

Step 1: Coefficient formula

Since $V_0 = 0$, the constant term of $W(z)$ is

$$ W_0 = U(V(0)) = U(U_0) = U_0. $$

For $n \ge 1$, we can write

$$ W_n = [z^n], U(V(z)) = \sum_{k=1}^n U_k ,[z^n] V(z)^k. $$

Define

$$ P_{k,n} := [z^n] V(z)^k, $$

so that

$$ W_n = \sum_{k=1}^n U_k P_{k,n}. $$

We now need an algorithm to compute $P_{k,n}$ efficiently.

Step 2: Recurrence for powers of $V(z)$

The sequence $P_{k,n}$ satisfies the convolution recurrence

$$ P_{1,n} = V_n, \qquad n \ge 1, $$

and for $k \ge 2$,

$$ P_{k,n} = \sum_{j=1}^{n-1} V_j , P_{k-1,n-j}, \qquad n \ge 1. $$

This follows from

$$ V(z)^k = V(z) \cdot V(z)^{k-1} \implies [z^n] V(z)^k = \sum_{j=1}^{n} V_j ,[z^{n-j}] V(z)^{k-1} = \sum_{j=1}^{n-1} V_j , P_{k-1,n-j}, $$

because $V_0 = 0$.

Step 3: Correct computation order

To implement this recurrence, we must compute the $P_{k,n}$ in an order such that all terms $P_{k-1,n-j}$ needed on the right-hand side are already available. This can be done using row-wise dynamic programming:

  1. Compute $P_{1,n}$ for $n = 1,\dots,N-1$.
  2. For $k = 2$ to $N-1$, compute $P_{k,n}$ for $n = k,\dots,N-1$ using the recurrence.

This guarantees that when computing $P_{k,n}$, all $P_{k-1,m}$ with $m < n$ are already known. In other words, we fill the table row by row (increasing $k$) and within each row from left to right (increasing $n$).

Step 4: Online algorithm

We now give a fully specified algorithm that computes $W_0,\dots,W_{N-1}$.

Algorithm C (Composition of power series):

C1. [Initialize.]

  • Set $W_0 \gets U_0$.
  • For $n = 1$ to $N-1$, set $P_{1,n} \gets V_n$.

C2. [Compute $P_{k,n}$ for $k \ge 2$.]

  • For $k = 2$ to $N-1$:

  • For $n = k$ to $N-1$:

$$ P_{k,n} \gets \sum_{j=1}^{n-1} V_j , P_{k-1,n-j}. $$

C3. [Compute $W_n$.]

  • For $n = 1$ to $N-1$:

$$ W_n \gets \sum_{k=1}^{n} U_k , P_{k,n}. $$

C4. [Output.] Output $W_0,\dots,W_{N-1}$.

This ordering ensures that all required $P_{k-1,m}$ values are available when needed.

Step 5: Correctness

  • Base case: $W_0 = U_0$ is correct.
  • Recurrence correctness: By induction on $k$, $P_{k,n}$ correctly represents $[z^n] V(z)^k$ for all $1 \le k \le n$.
  • Ordering correctness: By computing rows in increasing $k$ and within each row increasing $n$, all terms $P_{k-1,n-j}$ are available when computing $P_{k,n}$.
  • Composition correctness: Then $W_n = \sum_{k=1}^n U_k P_{k,n}$ is exactly the coefficient of $z^n$ in $U(V(z))$.

Hence the algorithm correctly computes the first $N$ coefficients of $U(V(z))$.

Step 6: Complexity

  • Computing $P_{k,n}$: Each $P_{k,n}$ requires $n-1$ multiplications. The number of entries $(k,n)$ with $1 \le k \le n \le N-1$ is approximately $N^2/2$. Therefore, the total number of multiplications for all $P_{k,n}$ is

$$ \sum_{n=1}^{N-1} \sum_{k=1}^{n} (n-1) = \sum_{n=1}^{N-1} n (n-1) = \sum_{n=1}^{N-1} (n^2 - n) = \frac{(N-1)N(2N-1)}{6} - \frac{(N-1)N}{2} = \frac{N^3}{3} - O(N^2) = O(N^3). $$

  • Computing $W_n$ for $n = 1$ to $N-1$ requires $\sum_{n=1}^{N-1} n = O(N^2)$ multiplications, negligible compared with $O(N^3)$.

Hence the total complexity is $O(N^3)$.

  • If $U_k = 0$ for $k > K$, the sum over $k$ can be truncated at $k = \min(n,K)$, reducing operations.
  • Faster algorithms using divide-and-conquer or FFT-based convolution can reduce the complexity to $O(N \log^2 N)$ for large $N$.

Step 7: Remarks

  1. The algorithm is online: $W_n$ can be output as soon as the $n$th column of $P_{k,n}$ is computed.
  2. This is a standard dynamic programming approach for series composition.
  3. The previous algorithm failed because it did not specify a computation order that satisfies data dependencies.

∎

This completes a correct and fully specified solution for computing the first $N$ coefficients of $U(V(z))$.