Interpolation of Polynomials

During the evalution step,

<values>=FFT(<coefficients>,ω)<\text{values}>=FFT(<\text{coefficients}>,\omega)

It turns out that during interpolation,

<coefficients>=1nFFT(<values>,ω−1)<\text{coefficients}> = \frac{1}{n}FFT(<\text{values}>,\omega^{-1})

To get a clearer view of interpolation, we can write out the relationship between two representations of polynomial A(x)A(x)

[A(x0)A(x1)⋮A(xn−1)]=[1x0x02⋯x0n−11x1x12⋯x1n−1⋮⋮⋮⋱⋮1xn−1xn−12⋯xn−1n−1][a0a1⋮an−1]\begin{bmatrix} A(x_0) \\ A(x_1) \\ \vdots \\ A(x_{n-1}) \end{bmatrix} = \begin{bmatrix} 1 &x_0 &x_0^2 &\cdots &x_0^{n-1} \\ 1 &x_1 &x_1^2 &\cdots &x_1^{n-1} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ 1 &x_{n-1} &x_{n-1}^2 &\cdots &x_{n-1}^{n-1} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_{n-1} \end{bmatrix}

The matrix in the middle, MM, is a Vandermonde matrix such that:

If x0,…,xn−1x_0, \dots, x_{n-1} are distinct numbers, then MM is invertible

and Vandermonde matrices also have the distinction of being quicker to invert O(n2)O(n^2) than more general matrices O(n3)O(n^3)

So…

🔥
Evaluation is multiplication by MM, while interpolation is multiplication by M−1M^{-1}

In FFT, since all x0,…,xn−1x_0, \dots, x_{n-1} are n-th root of unity, we can write our matrix M(ω)M(\omega) as

Mn(ω)=[1ω0(ω0)2⋯(ω0)n−11ω1(ω1)2⋯(ω1)n−1⋮⋮⋮⋱⋮1ωn−1(ωn−1)2⋯(ωn−1)n−1]=[111⋯11ωω2⋯ωn−1⋮⋮⋮⋱⋮1ω(n−1)ω2(n−1)⋯ω(n−1)(n−1)]\begin{split} M_n(\omega)&=\begin{bmatrix} 1 &\omega^0 &(\omega^0)^2 &\cdots &(\omega^0)^{n-1} \\ 1 &\omega^{1} &(\omega^1)^2 &\cdots &(\omega^1)^{n-1} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ 1 &\omega^{n-1} &(\omega^{n-1})^{2} &\cdots &(\omega^{n-1})^{n-1} \end{bmatrix} \\ &=\begin{bmatrix} 1 &1 &1 &\cdots &1 \\ 1 &\omega &\omega^2 &\cdots &\omega^{n-1} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ 1 &\omega^{(n-1)} &\omega^{2(n-1)} &\cdots &\omega^{(n-1)(n-1)} \end{bmatrix} \end{split}

Notice that for Mn(ω)M_n(\omega), its (j,k)(j,k) th entry (start counting from 0) is ωjk\omega^{jk}

🔥
The columns of M=Mn(ω)M = M_n(\omega) are orthogonal to each other, therefore they can be thought of as the axes of an alternative coordinate system, which is often called the Fourier basis.

The FFT is thus a change of basis, a rigid rotation. The inverse of M is the opposite rotation, from the Fourier basis back into the standard basis. When we write out the orthogonality condition precisely, we will be able to read off this inverse transformation with ease:

Mn(ω)−1=1nMn(ω−1)M_n(\omega)^{-1}=\frac{1}{n}M_n(\omega^{-1})

But notice ω−1\omega^{-1} is also an n-th root of unity, an therefore interpolation is basically just an FFT operation but with ω\omega replaced by ω−1\omega^{-1}

Lemma 1: The columns of matrix MM are orthogonal to each other

Take the inner product of any columns jj and kk of matrix MM

1+ωj−k+ω2(j−k)+⋯+ω(n−1)(j−k)1 + \omega^{j-k} + \omega^{2(j-k)}+\cdots+\omega^{(n-1)(j-k)}

Its a geometric series with first term 11, last term ω(n−1)(j−k)\omega^{(n-1)(j-k)}, ratio ω(j−k)\omega^{(j-k)}, converges to

1−ωn(j−k)1−ω(j−k)\frac{1-\omega^{n(j-k)}}{1-\omega^{(j-k)}}

Which evalutes to 0 when j≠kj \ne k, and evalutes to nn when j=kj = k

Therefore

MM∗=nIMM^* = nI

the (j,k)(j, k)th entry of M∗M^∗ is the complex conjugate of the corresponding entry of MM, ω−jk\omega^{-jk}, therefore MM = Mn(ω−1)M_n(\omega^{-1})