Inverse of a toeplitz matrix with fft based methods

How can I calculate the inverse of the matrix with fft based methods rather than the conventional ones like Cholesky decomposition, QR factorization or Eigen value decomposition or other Toeplitz inversion methods like Levinson-trench or berlekamp-massey? Can anyone tell me how can I do that in matlab please?

[Matt J]

Is the Toeplitz matrix also circulant? If not, I don't think it's possible.

If it were possible, why wouldn't everybody use FFT methods? They're O(N*logN) whereas the other methods have higher complexity.

[Chris Turnes]

There are methods based in the FFT to compute the inverse of a Toeplitz matrix, but they are not trivial to implement, and require quite a bit of background knowledge before you can go about doing it (they are O(N log^p N), with non-trivial overhead constant).

Long story short, you need to do some fancy tangential interpolation at the roots of unity to solve for the first and last columns of the inverse.