0
$\begingroup$

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.

enter image description here

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ I understand the explanations regarding the run time complextiy of the algorithm, but could you perhaps show more into details the process fo the convolution calculation and the FFT in this problem? This is what my understanding is lacking and I can't really understand it from other explanations i read $\endgroup$ – S. Peter Jan 29 at 20:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.