9
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ @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 $\endgroup$ – Erik S Feb 7 '15 at 12:42
  • $\begingroup$ 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. $\endgroup$ – user14505 Feb 8 '15 at 15:29
12
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.