Recursive Inverse Fast Fourier Transform (FFT) Given a polynomial $A$ in point-value form consisting of the 4 points $(1,5)$, $(i, -1-2i)$, $(-1, -7)$ and $(-i,3-2i)$. Using the recursive inverse FFT algorithm to interpolate, I want to find the coefficients of $A$. 
My main issue with figuring this out is the inclusion of the imaginary numbers which is throwing me off. Can anyone explain how to do this step by step so I can follow along and truly understand how to do this. Thanks!
 A: I presume you know the FFT algorithm, but to make sure we're on the same page, I'll give a pseudocode version of it here
vector fft(<a[0], a[1], ... , a[n-1]>, n, w)
   if n = 1
      return <a[0]>
   vector even = fft(<a[0], a[2], ... , a[n-2]>, n/2, w^2)
   vector odd = fft(<a[1], a[3], ... , a[n-1]>, n/2, w^2)
   for i = 0, ... , n/2 - 1
      v[i] = even[i] + w^i * odd[i]
      v[i+n/2] = even[i] - w^i * odd[i]
   return v

Where $\omega$ is a primitive $n$-th root of 1. The forward FFT can be used to go from the coefficient vector of the polynomial $p(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}$ and produce the interpolation vector $\langle\; p(\omega^0), p(\omega^1), \dots, p(\omega^{n-1})\;\rangle$, which in your example is $\langle\;5, -1-2i, -7, 3-2i\;\rangle$.

The nice thing about the FFT is that it can be used in both directions, so you can start with the interpolation vector as input and use the same algorithm to get the coefficients of the polynomial that generated it. The only differences in this reverse FFT are that (1) instead of using the $\omega$ that was used to generate the interpolation vector in the first place, you must use $1/\omega$ as your primitive $n$-th root of 1 and (2) the result will be $n$ times the coefficient list, so your last step will be to divide each term in the result by $n$.
Here's what it would look like for your example, using $-i$ as the primitive 4-th root of 1:
fft(<5, -1-2i, -7, 3-2i>, 4, -i)              --> [-4i, 12+4i, -4+4i, 12-4i]
   fft(<5, -7>, 2, -1)           --> [-2, 12]
      fft(<5>, 1, 1)     --> [5]   
      fft(<-7>, 1, 1)    --> [-7]
   fft(<-1-2i, 3-2i>, 2, -1)     --> [2-4i, -4] 
      fft(<-1-2i>, 1, 1) --> [-1-2i]
      fft(<3-2i>, 1, 1)  --> [3-2i]

The four bottom-level function calls (where $n=1$) simply return their vector arguments.
The two calls, $\text{fft}(\langle\;5, -7\;\rangle, 2, -1)$ and $\text{fft}(\langle\;-1-2i, 3-2i\;\rangle, 2, -1)$  use the results from the bottom-level function calls, so, for example, the first returns $[(5)+(-7), (5)-(-7)] = [-2,12]$ and the second returns $[(-1-2i)+(3-2i),(-1-2i)-(3-2i)]=[2-4i, -4]$, as I indicated above.
The top-level call combines these two 2-vectors into a 4-vector using the appropriate powers of $1/\omega = -i$ as follows:
$$
\begin{align}
v_0 &= (-2) + (-i)^0(2-4i) = -2+(1)(2-4i) = -4i\\
v_2 & = (-2) - (-i)^0(2-4i) = -2-(1)(2-4i) = -4+4i\\
v_1 & = (12) + (-i)^1(-4) = 12+(-i)(-4) = 12+4i\\
v_3 & = (12) - (-i)^1(-4) = 12-(-i)(-4) = 12-4i
\end{align}
$$
Finally remembering to divide the answer by 4 we have the coefficients of the polynomial:
$$
\frac{1}{4}[\;-4i, 12+4i,-4+4i, 12-4i]=[-i, 3+i, -1+i, 3-i\;] 
$$
so the original polynomial was
$$
p(x) = -i+(3+i)x+(-1+i)x^2+(3-i)x^3
$$
You can check that this is indeed correct by substituting $x=1, i, -1, -i$ and showing (with frequent use of the fact that $i^2=-1$) that this gives you the original interpolation vector.
