# 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. The method that you're trying to use fundamentally only works for circulant systems.
Furthermore, your $$a$$ vector doesn't have the "-1" in it anywhere, so you clearly don't have sufficient information.
A method that involves embedding the $$n$$ by $$n$$ Toeplitz matrix in a double-sized circulant matrix and doing an FFT on a vector of length $$2n$$ is described in
• Could you elaborate the answer? As Circulant Matrix is rectangular it means you need to extend $\boldsymbol{x}$ as well. – Royi Jan 11 '20 at 20:25