# 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 Feb 7, 2015 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, 2015 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

R. Kumar. A Fast Algorithm for Solving a Toeplitz System of Equations. IEEE Transactions on Acoustics, Speech, and Signal Processing 33(1): 1985. https://doi.org/10.1109/TASSP.1985.1164492

• Thank you Mr. Borchers. I misunderstood some concepts, you corrected them.
– Ömer
May 15, 2013 at 23:43
• Could you elaborate the answer? As Circulant Matrix is rectangular it means you need to extend $\boldsymbol{x}$ as well.
– Royi
Jan 11, 2020 at 20:25
• Methods for solving circulant linear systems are discussed in On the Solution of Circulant Linear Systems by Mingkui Chen doi.org/10.1137/0724044 Jan 12, 2020 at 21:07