Evaluation and Interpolation

The entire transform rests on one observation, and the observation involves no roots of unity, no modular arithmetic, and nothing more advanced than plotting points. It is worth meeting it in that plain form first.

01.A polynomial is determined by its values

Take a polynomial of degree at most $1$, that is, a straight line $a(X) = a_0 + a_1 X$. Two numbers describe it: $a_0$ and $a_1$.

Two other numbers also describe it. Pick any two distinct inputs, say $X = 0$ and $X = 1$, and record the outputs $a(0)$ and $a(1)$. Those two values pin the line down completely, because two points determine a line.

The same holds at every degree. A polynomial of degree at most $n - 1$ has $n$ coefficients, and it is equally determined by its values at any $n$ distinct points. Going one way is evaluation. Going back is interpolation.

So there are two equally valid ways to store a polynomial.

Coefficient form. The list $(a_0, a_1, \ldots, a_{n-1})$.

Point-value form. The list $\bigl(a(x_0), a(x_1), \ldots, a(x_{n-1})\bigr)$, for some agreed set of $n$ distinct points.

Neither loses information. They are two encodings of the same object.

02.Multiplication is cheap in the second form

Here is why anybody cares.

Suppose $a$ and $b$ are both stored in point-value form, at the same points. What is the point-value form of their product $c = ab$?

At each point $x_i$,

$$c(x_i) \;=\; a(x_i) \cdot b(x_i) .$$

That is it. One multiplication per point. The value of a product at a point is the product of the values, which is true because that is what multiplying functions means.

So in point-value form, multiplying two polynomials of any degree costs $n$ multiplications rather than $n^2$. Linear, not quadratic.

Work it concretely with two lines. Let $a(X) = 1 + 2X$ and $b(X) = 3 + X$, and evaluate at $X = 0, 1, 2, 3$.

Check the last column against the true product, which is $ab = 3 + 7X + 2X^2$. At $x = 2$ that gives $3 + 14 + 8 = 25$. Correct. At $x = 3$, $3 + 21 + 18 = 42$. Correct.

Four points were used rather than three because the product has degree $2$ and so needs three values to determine it, and taking one extra costs nothing.

03.The round trip

That suggests an algorithm immediately.

1. Evaluate $a$ at $n$ points.
2. Evaluate $b$ at the same $n$ points.
3. Multiply the values pointwise. Cost: $n$ multiplications.
4. Interpolate back to coefficient form.

Step 3 is wonderfully cheap. Steps 1, 2 and 4 are the problem.

Evaluating a polynomial with $n$ coefficients at one point costs about $n$ multiplications by Horner's method. Doing that at $n$ separate points costs $n^2$, which is exactly what we were trying to avoid. Interpolation by the standard method is no better.

So the round trip as described saves nothing. The expensive part simply moved.

04.Where the saving comes from

The way out is to stop treating the evaluation points as arbitrary.

Nothing so far constrained them. Any $n$ distinct points work. That freedom is the opening: if the points are chosen with a particular relationship to one another, evaluating at all of them at once can share work, and the shared work collapses the cost from $n^2$ to $n \log n$.

The relationship that does it is this. Choose the points so that they are the powers of a single element $\omega$, that is

$$x_0 = \omega^0, \quad x_1 = \omega^1, \quad x_2 = \omega^2, \; \ldots, \; x_{n-1} = \omega^{n-1},$$

where $\omega$ has the property that $\omega^n = 1$ and no smaller positive power of $\omega$ equals $1$. Such an $\omega$ is called a primitive $n$th root of unity.

Why that helps is worth seeing rather than taking on trust. Split $a$ into its even-indexed and odd-indexed coefficients, writing

$$a(X) \;=\; a_{\text{even}}(X^2) \;+\; X \cdot a_{\text{odd}}(X^2),$$

where each half has $n/2$ coefficients. To evaluate $a$ at all $n$ points, you need $a_{\text{even}}$ and $a_{\text{odd}}$ at the squares of those points.

Now the special property does its work. Squaring the $n$ powers of $\omega$ does not give $n$ different values. It gives only $n/2$, because $\omega^{k + n/2}$ squares to the same thing as $\omega^k$. So the two half-sized problems are evaluated at half as many points, and the recursion halves the work at every level rather than merely splitting it.

That gives the recurrence

$$T(n) \;=\; 2\,T(n/2) \;+\; O(n),$$

whose solution is $O(n \log n)$. Two subproblems of half the size, plus linear work to recombine. This is the Cooley-Tukey structure, and The Butterfly and Bit Reversal writes out every step of it for $n = 4$.

05.One complication to flag now

There is a mismatch that has to be dealt with, and it is easier to name here than to discover later.

The construction above computes the product modulo $X^n - 1$, not modulo $X^n + 1$. The reason is direct: the evaluation points satisfy $\omega^n = 1$, so any multiple of $X^n - 1$ evaluates to zero at every one of them and is invisible to the transform.

That is the cyclic convolution, where the coefficient that overflows past degree $n$ wraps around and is added back at the bottom.

$R_q$ needs the negacyclic version, where the overflow wraps around and is subtracted, because $X^n = -1$.

Fixing the mismatch requires evaluation points satisfying $x^n = -1$ rather than $x^n = +1$. Those exist, and finding them is the subject of the next note.