Multiply a circulant matrix by a vector with FFT.

Question

I am asked to write a Matlab program to find the coefficients of the resulting polynomial which is the product of two other polynomials. However, I need someone to clarify the underlying concepts for me. In this post, I will use $P_a(x)=1+2x+3x^2$ and $P_b=1+2x+3x^2+4x^3$ as our examples for the two polynomials. Using matrix formulation (which is the requirement): $$ a = \left(\begin{array}{c} 1\\ 2\\ 3\\ 0\\ 0\\ 0\end{array} \right) \qquad b = \left(\begin{array}{c} 1\\ 2\\ 3\\ 4\\ 0\\ 0\\\end{array} \right) $$ And we are looking for the vector $c$ that is the coefficients of our product polynomial. Since the degree of the resulting polynomial is $5$, we will have $6$ coefficients including the constant term. And I know that $c$ is a product of the circulant matrix of $a$ and the vector $b$: $$ c = \left(\begin{array}{c} c_0\\ c_1\\ c_2\\ c_3\\ c_4\\ c_5\end{array} \right)= \left(\begin{array}{cccccc} 1&0&0&0&3&2\\ 2&1&0&0&0&3\\ 3&2&1&0&0&0\\ 0&3&2&1&0&0\\ 0&0&3&2&1&0\\ 0&0&0&3&2&1\\ \end{array} \right) \>\dot\ \>\left(\begin{array}{c} 1\\ 2\\ 3\\ 4\\ 0\\ 0\\ \end{array} \right) $$ and we denote the circulant matrix $A$. I know I can construct $A$ by using $FFT$: $$ A = F^{-1}\>diag(F\,a)\>F $$ And here's what confuses me. From this point on, do I just multiply the matrix A by the vector b directly? I am required to implement the algorithm in $O(n\>logn)$ time. And Let me repeat the requirement: 1. Matrix formulation of the problem 2. Using FFT 3. Overall run time being $O(n\>logn)$ Any input is greatly appreciated. Thanks!

Answer 1

You can get $c$ by multiplying the decomposed $A$ by $b$.

Say the decomposed $A$ is , $A=F^{-1} diag(Fa)F$. Then, $c=Ab=F^{-1} diag(Fa)(Fb)$. This says that $c$ can be obtained by taking the IFFT of the vector $diag(Fa)(Fb)$. All you no need to do is, take the FFT of b, FFT a and compute c.