4
$\begingroup$

Is it known that if polynomial multiplication of degree $n$ polynomials and coefficient size bounded by $M$ can be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words then $FFT$ of length $n$ vectors with entries bound by $M$ can also be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words?

Note that the converse is trivial since polynomial multiplication reduces to $FFT$.

$\endgroup$
6
$\begingroup$

Suppose you have vectors $u$ and $v$. Imagine a table $M$ of the products of each of their entries.

$$M = |u\rangle\langle v| = \begin{bmatrix} u_0 v_0 & u_1 v_0 & u_2 v_0 & \dots & u_{n-1} v_0 \\ u_0 v_1 & u_1 v_1 & u_2 v_1 & \dots & u_{n-1} v_1 \\ u_0 v_2 & u_1 v_2 & u_2 v_2 & \dots & u_{n-1} v_2 \\ \vdots &\vdots &\vdots & \ddots & \vdots \\ u_0 v_{n-1} & u_1 v_{n-1} & u_2 v_{n-1} & \dots & u_{n-1} v_{n-1} \\ \end{bmatrix}$$

The convolution $u \ast v$ of the two vectors is a vector of the values you get when summing along each anti-diagonal of this grid. For example:

$$(u \ast v)_2 = \sum \begin{bmatrix} & & & & & & u_{n-3} v_0 & 0 & 0\\ & & & & & u_{n-4} v_1 \\ & & & & \ddots \\ & & & u_2 v_{n-5} & \\ & & u_1 v_{n-4} & & \\ u_0 v_{n-3} & & & & \\ 0 &\\ 0& \text{ } \end{bmatrix}$$

We can also think of the FFT of a vector as summing entries in a grid defined by multiplying two vectors' entries. The second vector is the sequence of roots of unity.

$$M = | u \rangle \langle e^{\tau i k/n} |\begin{bmatrix} u_0 & u_1 & u_2 & \dots & u_{n-1} \\ u_0 e^{\tau/n} & u_1 e^{\tau/n} & u_2 e^{\tau/n} & \dots & u_{n-1} e^{\tau/n} \\ u_0 e^{2\tau/n} & u_1 e^{2\tau/n} & u_2 e^{2\tau/n} & \dots & u_{n-1} e^{2\tau/n} \\ \vdots &\vdots &\vdots & \ddots & \vdots \\ u_0 e^{-\tau/n} & u_1 e^{-\tau/n} & u_2 e^{-\tau/n} & \dots & u_{n-1} e^{-\tau/n} \end{bmatrix}$$

The Fourier transform doesn't track along the diagonals, though. Its row-hop is different from its column-hop. For the $k$'th entry of the output we go through each column $c$ and sum up the cell from that column and the $k \cdot c$'th row (wrapping around).

$$FFT(v)_2 = \sum \begin{bmatrix} u_0 \\ &&&&u_4e^{\tau/7} \\ & u_1 e^{2\tau/7} \\ &&&&&u_5e^{3\tau/7} \\ & & u_2 e^{4\tau/7} \\ &&&&&&u_6e^{5\tau/7} \\ &&& u_3 e^{6\tau/7} \\ \end{bmatrix}$$

So our question becomes: can we somehow re-arrange our vectors so that the each-stride sums $\sum u_i v_{k \cdot i}$ correspond to the each-diagonal sums $\sum u_i v_{k-i}$? Can we turn index-multiplication into index-adding?

We can, as long as we're operating in a context that allows for a logarithm. Suppose our vector size is $n$ and $g$ is a multiplicative generator for the integers modulo $n$. Then we can use the powers of $g$, i.e. the base-$g$ discrete logarithm, to define a permutation of the non-zero elements that does most of what we need. Our transformation goes roughly as follows:

  • Define permuted vectors $a$ and $b$ so that $a_k = u_{g^k}$ and $b_k = v_{g^{k}}$.
  • Compute the convolution $c = a \ast b$. So $c_k = \sum_{d=0}^{n-1} a_d b_{k-d} = \sum_{d=0}^{n-1} u_{g^d} v_{g^{-k} \cdot g^d}$.
  • Now un-permute $c$, and also un-permute the sum over $d$. $x_{g^{-k}} = c_{k}$ and $e=g^d$. So $x_k = c_{\log_g k} = \sum_{e=0}^{n-1} u_{e} v_{k \cdot e}$.

In other words: define a permutation $P$ based on when indices are reached when iteratively multiplying by $g$. Permute the input vector and the vector of $e^{\tau k /n}$ powers by $P$. Convolve. Unpermute by $P$. The result is the Fourier transform.

... Except that I've ignored one important issue. Our permutation doesn't work for $k=0$, because $g^k \mod n$ is never 0. Also, $g^0 = g^{n-1} = 1$. Fixing this hole requires special-casing the edges of the grid. But hopefully I've communicated the core idea of performing an FFT by delegating the heavy-lifting to a convolution and a permutation.

Note that, if you care about bit complexity instead of the number of arithmetic operations, computing the permutation may also be an obstacle. If multiplying by $g \pmod{n}$ costs $\log n$ time, and you don't have the permutation ahead of time, then overall the algorithm will still cost $O(n \log n)$.

$\endgroup$
  • $\begingroup$ nice! a top/ std ref would be helpful $\endgroup$ – vzn Mar 17 '16 at 23:22
  • $\begingroup$ @vzn What's a top/std ref? $\endgroup$ – Craig Gidney Mar 17 '16 at 23:24
  • $\begingroup$ is this covered in any standard textbook that you know of? plz cite it if possible $\endgroup$ – vzn Mar 18 '16 at 1:17
  • $\begingroup$ @vzn Oh. I just came up with it after reading the question. No doubt it's been done before, and better, but I don't know where. $\endgroup$ – Craig Gidney Mar 18 '16 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy