Solving Ax=b by FFT I read in Wiki that it is possible to solve Ax=b via Fast Fourier Transform given that A is a circulant matrix. For example, I have  $\begin{bmatrix}
1 & 0 & 0 & -1 \\
-1 & 1 & 0 & 0 \\
0 & -1 & 1 & 0 \\
0 & 0 & -1 & 1 
\end{bmatrix}x=$$ \begin{bmatrix}
1 \\
0 \\
0 \\
-1 
\end{bmatrix}  $
where A is a circulant matrix.
How do I solve this system using FFT? I had a hard time understanding the concept. Any help is greatly appreciated. Thank you for your understanding.

We can use something called a similarity transform $A = F^{-1}DF$
For circulant matrices we can be sure that we can choose $F$ to be a DFT matrix and $D$ matrix will be a diagonal matrix with the Fourier coefficients of one row (or column).
This $F$ matrix is dense so so far we have not saved much by doing this transformation.
The FFT in matrix language is nothing else but a factorization of this $F$ matrix.
We can write $F = F_1F_2\cdots F_N$ . A product of matrices.
Now the neat part is that we can get these $F_k$ matrices to be sparse. Only two non-zero values every row no matter the size of the matrix.
We can show that $N$ here will be $\log_2(n)$ where $n$ is the side of $A$. Quite few matrices compared to the size.
So we will get away with all in all something like $n+4n\log(n)$ multiplications instead of $n^2$ multiplications if we are to do a matrix-vector multiplication.
