9

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?

J. M.
  • 3,155
  • 28
  • 37
Ömer
  • 643
  • 6
  • 10
  • @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 07 '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. –  Feb 08 '15 at 15:29

1 Answers1

14

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

Brian Borchers
  • 18,719
  • 1
  • 39
  • 70
  • Thank you Mr. Borchers. I misunderstood some concepts, you corrected them. – Ömer May 15 '13 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 '20 at 20:25
  • Methods for solving circulant linear systems are discussed in On the Solution of Circulant Linear Systems by Mingkui Chen https://doi.org/10.1137/0724044 – Brian Borchers Jan 12 '20 at 21:07