Calculate $Av^{\rightarrow}$ using FFT

Question

Given a vector $v^{\rightarrow} = (v_0,v_1, ... v_{n-1})$

And given the matrix A =

$(a_0, a_1 ... a_{n-1})$

$(a_{n-1}, a_0,...., a_{n-2})$

$(a_{n-2}, a_{n-1}, a_0,...., a_{n-3})$

.....

$(a_1, ..., a_{n-2}, a_{n-1}, a_0)$

Each row of the matrix is a circular movement of the row above one column to the right.

I need to calculate $A\cdot v^\rightarrow$ in $\Theta(n\cdot lg n)$ complexity

I understand that the result is in the form of the following vector.

The naive approach will take me $\theta(n^2)$. In order to that in the required complexity I know that FFT can come handy. But how do I define the polynomials that the algorithm will use? I saw a friend's solution but could not quite understand it. I really want an explanation to this problem and hopefully I will understand the basic concept of how to approach such problems.

Answer 1

Let $b=(b_0,...b_{n-1})$ with $b_i=a_{n-i}$ where the indices are taken modulo $n$ (reversing the order of the $a_i$'s makes it easier to bring up convolutions, see below).

Matrix $A$ has a special structure, which makes it amenable to fast computations. More precisely, it is a convolution matrix, which means that when you apply it to a vector $v$, the resulting vector is the convolution of $b$ with $v$: $$(A_v)_i=(b \circledast v)_i =\sum_{j}b_{i-j}v_j =\sum_{j}a_{j-i}v_j\text { (all indices modulo } n \text{)}$$ The Discrete Fourier Transform $\mathcal F$ maps a vector in $\mathbb R^n$ to another vector in $\mathbb R^n$ . It has the nice property of transforming a convolution into a component-wise product, that is: $$\left(\mathcal F(b \circledast v)\right)_i=(\mathcal F(b))_i(\mathcal F(v))_i$$ So once transformed by the Fourier transform, the resultof applying $A$ to $v$ can be computed in only $\mathcal O(n)$ operations (component-wise multiplications).

What's more, the Discrete Fourier transform, and its inverse, can be computed efficiently using the FFT algorithm, in $\mathcal O(n\log(n)$.

So this means that to compute $Av$, you can apply the following efficient algorithm:

• First, precompute the discrete Fourier transform $\mathcal F(b)$ of $b$ via the FFT. It's a one-time operation.
• For any vector $v$,
  • compute its discrete Fourier transform $\mathcal F(v)$ viat the FFT,
  • multiply, component-by-component, $\mathcal F(v)$ with $\mathcal F(b)$
  • Apply the inverse discrete Fourier transform (via the FFT) to the resulting vector.

For every vector $v$, this algorithm takes $\mathcal O(n\log(n)) + \mathcal O(n)+\mathcal O(n\log(n))=\mathcal O(n\log(n))$ operations, instead of the normal $\mathcal O(n^2)$.