Multiplication through evaluation
Let be integers. Write and ; a zero polynomial may be represented by the one-entry list . Their product has coefficient
Directly summing all coefficient pairs takes arithmetic operations. An alternative evaluates both polynomials at chosen points, multiplies the values pointwise, and recovers the coefficients. Roots of unity permit these evaluations to share work. We first use exact complex arithmetic; practical floating-point behavior is a separate question.
Choose a power of two and append zeros to both coefficient lists until they have length .
Definition 10.1.1
(Discrete Fourier transform)
Let , a primitive th root of unity. For a length- list , the discrete Fourier transform is
These are the values of the polynomial at . The positive exponent is our convention; the inverse below uses the opposite sign.
Inversion and cyclic convolution
Theorem 10.1.2
(Inversion formula)
For every length- list ,
Proof
(A vanishing geometric sum)
For integers the finite geometric sum obeys
If , every term is . Otherwise primitivity of makes the ratio different from one, while its th power is one, so the geometric sum vanishes. Multiplying by and summing over gives
because only survives for .
Definition 10.1.3
(Cyclic convolution)
For length- lists , their cyclic convolution is the length- list
Theorem 10.1.4
(Pointwise products give cyclic convolution)
If is the cyclic convolution of and , then for every . Hence applying the inverse transform to the pointwise products returns . If are the coefficient lists of padded to length , then is the list of ordinary product coefficients followed by zeros.
Proof
(Exponents add, and no term wraps)
We have . Since , the exponent depends only on , so collecting terms with gives . The inversion formula then recovers from these values.
For the padded lists, for and for , so a nonzero term has . Then with means , so for , and above that.
Concept lensStructural
Cyclic convolution as multiplication modulo $x^n$ - 1
The same objects have a second description. The points are exactly the distinct roots of , and reduces to modulo . So the cyclic convolution of and is the coefficient list of , and the transform is the map that records this remainder by its values at the roots. Pointwise multiplication of values is then the multiplication of remainders, and the inversion formula says that a remainder of degree below is determined by those values. Aliasing is the reduction itself: a product of degree or more is not equal to its remainder.
Padding is therefore not optional.
Counterexample mode
Too little padding folds the product
A plausible shortcut is to pick from the input lengths alone and trust the inverse transform to return the ordinary product. With and , the ordinary product is . Cyclic convolution of with itself has and , giving the list : the coefficient wrapped into the constant position, which also appears as . The repair is to choose ; here keeps all three coefficients separate.
Divide the transform into even and odd indices
Assume is a power of two. Split the coefficient list into its even-index and odd-index entries, defining and . Then
Since is a primitive th root, recursively evaluate both length- lists at its powers. Call the resulting transforms and .
Theorem 10.1.5
(Radix-2 FFT)
For a power of two and ,
Computing the transform recursively by these formulas, with when , takes arithmetic operations for if the powers of are available or generated in linear work per level.
Proof
(Induction on the size, then the recurrence)
For the transform of is . For and , split the defining sum by parity of the index:
where the inner sums are the transforms of the half-length lists with root , correct by the induction hypothesis. For the index we have , and because . This gives the second formula.
The two half-size problems and combination work give , whose solution is for .
Proof X-ray
What the two combination formulas rely on
The proof uses three facts about and each has a separate job. That is a primitive th root makes the two half-size problems instances of the same problem, which is what allows the induction. The identity is what lets one pair of half-size values produce two outputs, and , at the cost of one multiplication by ; this halves the work and is the source of the logarithm. Finally, must be a power of two so that the halving can continue until without a leftover odd size. The inverse transform reuses the same recursion because is also a primitive th root, followed by division by from the inversion formula. Two forward transforms, pointwise multiplication and one inverse therefore cost arithmetic operations.
A four-point example
Worked example 10.1.6
(Multiply 1 + 2x by 1 + x + with four points)
Take and . Their product degree is at most three, so is enough. With , evaluating at gives:
| List | Value at | Value at | Value at | Value at |
|---|---|---|---|---|
| 3 | ||||
| 3 | 1 | |||
| pointwise product | 9 |
Applying the inverse formula to the last row gives , so . For instance, the coefficient of is . The product has degree at most three, so this length-four transform cannot fold any nonzero product term into a lower coefficient.
Worked example 10.1.7
(One butterfly pass for the transform of 1 + 2x)
Pad to with and . The even entries and the odd entries are transformed with at size two: and . The combinations give
which agree with the first row of the table above. Each of the two half-size values is used twice, once with a plus and once with a minus sign.
Worked example 10.1.8
(Padding beyond the minimum)
Multiply , so and . The smallest power of two at least is , not . The product is , so the inverse returns , with three trailing zeros. As a check, , the pointwise product at is , and the output coefficients sum to . The extra zeros are harmless; only too few outputs would fold terms together.
Costs and numerical limits
The arithmetic-operation bound treats complex additions and multiplications as constant cost. It is not a bit-complexity bound for arbitrarily large exact coefficients, nor does it promise exact answers in floating-point arithmetic. Rounding reconstructed integer coefficients is justified only when an independently established error bound puts each computed real coefficient within of its true integer value; imaginary roundoff must also be handled. Exact modular transforms or arbitrary-precision methods require their own root, modulus and reconstruction conditions.
Common mistakes
Common mistake
(Applying the forward transform twice instead of inverting)
Reusing the forward formula for the inverse omits both the sign change and the factor . For , the list has transform . Applying the forward transform again gives , which is times with its index reversed modulo , not . Use and divide by .
Common mistake
(Thinking convolution needs a power of two)
The inversion formula and the cyclic convolution theorem hold for every with . A power of two is needed only for the radix-2 splitting that makes the transform fast. If is not a power of two, the definitions are still correct; the recursion above simply does not apply as written.
Exercises
Quick check
(For , compute the transform of under the positive-exponent convention.)
Use with .
Solution · Answer
Since , , so the transform is .
Quick check
(Explain why suffices for multiplying polynomials of degrees at most one and two, but need not suffice.)
Count the coefficients of the product.
Solution · Answer
The product has degree at most , so four coefficients, and . With , terms of degree and wrap onto degrees and . For the length-two cyclic result is , not the product coefficients.
Quick check
(If at the four roots, use the inverse formula to recover . Which coefficient list gives this transform?)
Evaluate for each .
Solution · Answer
For the sum is . For it is a geometric sum of the nontrivial powers of , which vanishes. So , the constant polynomial , whose values are at every point.
Quick check
(Use the butterfly formulas with to compute the transform of .)
The even entries are and the odd entries are .
Solution · Answer
The even half transforms to . The odd half transforms to at size two. With : , , , . This is the list , the values of the polynomial at the four roots.