Solving linear systems by fft

Question

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?

Answer 1

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.