Lagmental Vicfred

FFT Splits a Polynomial into Even and Odd Coefficients by Vicfred

Evaluation at n-th roots of unity reduces recursively to two transforms of half the size. The formulas are more useful when each symbol has a job rather than merely decorating the theorem.

The data

Fast algebraic algorithms exploit structure in a transform, matrix, or convex objective. The Fourier transform evaluates \(A(x)\) at roots \(\omega_n^k\), while linear-programming duality supplies certificates.

$$ A(x)=A_{\mathrm{even}}(x^2)+xA_{\mathrm{odd}}(x^2) $$

The typography mirrors the proof: first declare \(\mathsf D\), then state \(\mathsf C\). The symbol \(\Longrightarrow\) below is a logical dependency, not extra mathematical structure.

$$ A(\omega_n^k)=A_{\mathrm{even}}(\omega_{n/2}^k)+\omega_n^kA_{\mathrm{odd}}(\omega_{n/2}^k) $$

Derivation

This is the algebraic core of the note. Once this line is correct, the surrounding interpretation has something solid to refer to.

$$ \begin{pmatrix}A(\omega_n^k)\\A(\omega_n^{k+n/2})\end{pmatrix}=\begin{pmatrix}1&\omega_n^k\\1&-\omega_n^k\end{pmatrix}\begin{pmatrix}A_{\mathrm{even}}(\omega_{n/2}^k)\\A_{\mathrm{odd}}(\omega_{n/2}^k)\end{pmatrix} $$

Invariant content

The invariant statement is the one that does not depend on a convenient choice of coordinates, representatives, basis, or enumeration.

$$ \begin{aligned} \mathsf{D}\;&:\quad A(x)=A_{\mathrm{even}}(x^2)+xA_{\mathrm{odd}}(x^2),\\[5pt] \mathsf{C}\;&:\quad A(\omega_n^k)=A_{\mathrm{even}}(\omega_{n/2}^k)+\omega_n^kA_{\mathrm{odd}}(\omega_{n/2}^k). \end{aligned} $$

Scope

An asymptotically fast method still needs algebraic preconditions: an NTT modulus needs suitable roots, and convex-hull optimization needs monotone slopes or queries for its simplest form.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] A(\omega_n^k)=A_{\mathrm{even}}(\omega_{n/2}^k)+\omega_n^kA_{\mathrm{odd}}(\omega_{n/2}^k) \end{gathered}} $$

I would use the boxed line as a reference later, while returning to the full display whenever a hypothesis becomes uncertain. That division keeps compression from becoming ambiguity.

This article was posted on Tue 14 August 2018. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.