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?