Exact roots-of-unity Cauchy matvec has quasi-linear arithmetic cost

For a leaf containing index $j$, $P_j(z)\mathrm{/}{D}_j(z)=a_j\mathrm{/}(z-{\mu }_j)$ whenever $z\mathrm{\ne }{\mu }_j$. If the identity $P_I\mathrm{/}{D}_I={\sum }_{j\in I}{a}_j\mathrm{/}(z-{\mu }_j)$ holds for the two child sets, then the internal-node formulas in [F1] give $P_I\mathrm{/}{D}_I=P_{I_1}\mathrm{/}{D}_{I_1}+P_{I_2}\mathrm{/}{D}_{I_2}$. Induction up the finite tree therefore gives $P_I(z)\mathrm{/}{D}_I(z)={\sum }_{j=1}^n{a}_j\mathrm{/}(z-{\mu }_j)$ at the root wherever its denominator is nonzero.

The balanced tree has height at most $\lceil {\log }_{2}n\rceil$. At a node whose index set has size $s$, its three polynomial products have operand degrees at most $s$; by [F2] they cost $O(s\log (2+s))$ operations. At a fixed height, the node index sets are disjoint and their sizes sum to at most $n$, so that height costs at most $O(n\log (2+n))$. Summing over the height gives $O(n{\log }^2(2+n))$ operations, including the coefficient additions. A depth-first evaluation stores at most one completed sibling subtree per level; their coefficient-array sizes form a geometric sum bounded by $O(n)$, so the product-tree workspace is $O(n)$.

Write the root coefficients as $P_I(z)={\sum }_j{p}_j{z}^j$ and $D_I(z)={\sum }_j{d}_j{z}^j$. For each $0\le r<M$, fold them to $p_r^{\mathrm{\prime }}={\sum }_{j\equiv r(\mathrm{m}\mathrm{o}\mathrm{d}M)}{p}_j$ and $d_r^{\mathrm{\prime }}={\sum }_{j\equiv r(\mathrm{m}\mathrm{o}\mathrm{d}M)}{d}_j$. Since ${\omega }^{kM}=1$, evaluating the folded polynomials at ${\omega }^k$ gives exactly $P_I({\omega }^k)$ and $D_I({\omega }^k)$. The algorithm evaluates both folded arrays with two radix-two DFTs on the standard grid ${\omega }_0^j=e^{-2\pi ij\mathrm{/}M}$; if $M>1$, the supplied primitive root is $\omega ={\omega }_0^s$ for a unique odd $s$, so reindexing the standard outputs at $sk<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>M$ gives their values at ${\omega }^k$. For $M=1$ the grids coincide. By [F2] the two transforms cost $O(M\log (2+M))$ operations and $O(M)$ additional space; finding $s$ and reindexing cost $O(M)$ operations and space, within the same bounds. Folding costs $O(n)$ operations and $O(n+M)$ space.

The noncollision hypothesis makes $D_I({\omega }^k)={\prod }_j({\omega }^k-{\mu }_j)\mathrm{\ne }0$ for every $k$. Thus the divisions in [F1] are defined, and step 1.1 identifies each quotient with the required Cauchy sum. Adding the product-tree, folding, transform, and division costs gives $O((n+M){\log }^2(2+n+M))$ operations and $O(n+M)$ space.