Product of a vector by an inverse of Toeplitz matrix

Question

It is well known that using fast Fourier transform it's possible to multiply a vector by a Toeplitz matrix $A \cdot v = w$ in $n\cdot\log(n)$ operations. I read somewhere that also the product of a vector by the inverse of Toeplitz matrix $A^{-1} \cdot v = w$ can be done in $n\cdot\log(n)$ operations, but I don't understand how.

Is it possible to invert a generic Toeplitz matrix so quickly? Or the fast Fourier transform method also works by inverting the values? I don't need the inverse matrix, only perform the product $A^{-1} \cdot v = w$ as quickly as possible.

Answer 1

While $O(n\log^2n)$ Toeplitz solvers have been known for a while, they tend to be numerically unstable. The modern approach is to use FFTs to convert the problem to one involving Cauchy matrices, and then to represent this Cauchy matrix to high accuracy using a structured low-rank representation, typically a sequentially semi-separable (SSS) representation, and then solve the resulting system in $O(n)$ flops. I do note that this is not an exact solver, but you can easily achieve double precision backward error accuracy, as the dependence on the accuracy is only logarithmic. One realization of this approach is given in the reference: https://www.math.purdue.edu/~xiaj/work/toep.pdf.