I read in a paper and also at wiki that we can solve the system $$Ax=B$$ by Fast Fourier Transform, where $A$ is a circulant matrix. The solution is $$x=\mathtt{ifft}(\mathtt{fft}(B)/\mathtt{fft}(a))$$ where $a$ is first column of $A$, ifft is the inverse of fft and $/$ denotes component-wise division. For example, the solution of the following system $$\begin{pmatrix} 2 & -1 & 0 & 0 & 0\\ 1 & 2 & -1 & 0 & 0\\ 0 & 1 & 2 & -1 & 0\\ 0 & 0 & 1 & 2 & -1\\ 0 & 0 & 0 & 1 & 2 \end{pmatrix}x=\begin{pmatrix} 2\\ 2\\ -4\\ 7\\ -6 \end{pmatrix}$$ is $$x=\begin{pmatrix} 1\\ 0\\ -1\\ 2\\ -4 \end{pmatrix}$$ But when I implement $$x=\mathtt{ifft}(\mathtt{fft}(B)/\mathtt{fft}(a))$$, I get

$$x=\begin{pmatrix} \frac{118}{33}\\ - \frac{26}{33}\\ - \frac{53}{33}\\ \frac{142}{33}\\ - \frac{170}{33} \end{pmatrix}$$

What is my fault?

  • $\begingroup$ @BrianBorchers: Can you please elaborate how to embed a matrix A into a circulant matrix. How would I zero pad the example above? How is the right hand side (vector B) padded? Thank you Erik $\endgroup$ – Erik S Feb 7 '15 at 12:42
  • $\begingroup$ I don't think you can use FFTs to solve a Toeplitz system rigourously. If it were possible, I don't see why there would be any need for the Levinson algorithm, which was expressly developed for solving Toeplitz systems. $\endgroup$ – user14505 Feb 8 '15 at 15:29

Your matrix $A$ isn't a circulant matrix- it's just Toeplitz. Furthermore, your $a$ vector doesn't have the "-1" in it anywhere, so you clearly don't have sufficient information.

The standard remedy for this is to embed $A$ in a larger matrix which actually is a circulant matrix by padding the vectors with 0's and correctly handling the "-1" (which belongs at the end of the first column of the circulant matrix. You'll end up with a system of $2n$ equations in $2n$ unknowns, but the speed to of the FFT will more than makeup for this increase in the size of the system.

  • $\begingroup$ Thank you Mr. Borchers. I misunderstood some concepts, you corrected them. $\endgroup$ – Ömer May 15 '13 at 23:43

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.