# Solving linear systems by fft

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?

• @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 – Erik S Feb 7 '15 at 12:42
• 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. – 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.