I am trying to work through the 2017 paper A new Toeplitz inversion formula, stability analysis and the value by Yanpeng Zhenga, Zunwei Fub, and Sugoog Shona.
In this paper the authors present a fast $O(n log(n))$ Toeplitz inversion formula. However, there are some details that seem to be lacking for those wishing to replicate the algorithm.
Here is the relevant part of the paper:
$\newcommand\iddots{\mathinner{ \kern1mu\raise1pt{.} \kern2mu\raise4pt{.} \kern2mu\raise7pt{\Rule{0pt}{7pt}{0pt}.} \kern1mu }}$
Let $ T=(a_{i-j=1}^{n}) $ be an $n \times n$ Toeplitz matrix, then it satisfies the formula:
$$ \Xi T - T\Xi = ve_n^T - e_1v^TJ $$
where
$$ \Xi = \begin{pmatrix} 0 &&& -1 \\ 1 & \ddots && \\ & \ddots & \ddots & \\ && 1 & 0 \end{pmatrix}, J = \begin{pmatrix} &&& 1 \\ && 1 & \\ & \iddots && \\ 1 &&& \end{pmatrix} $$
$$ e_1 = \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, e_n = \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1 \end{pmatrix}, v = \begin{pmatrix} 0 \\ a_{1-n} + a_1 \\ \vdots \\ a_{-2} + a_{n - 2} \\ a_{-1} + a_{n - 1} \end{pmatrix}. $$
$$ $$
The paper implies there is a solution to $Tx = v, Ty = e_1$ without inverting the matrix $T$. I believe using $T^{-1}$ to solve $Tx = v, Ty = e_1$ would defeat the point of the paper.
My question is: Can anyone explain to me how $x$ and $y$ might be solved using the given equations without inverting $T$?
Obviously $Tx = v, Ty = e_1$ could be solved for $x, y$ using a Toeplitz solver or by direct inversion of $T$. But, again this would seem to invalidate the point of the paper. My guess is that combining and rearranging $\Xi T - T\Xi = ve_n^T - e_1v^TJ$ and $Tx = v, Ty = e_1$ in some way will provide expressions for $x, y$ that do not require $T^{-1}$.
After some research it looks like the special forms of $v, e_1, e_n$ allow $Tx=v,Ty=e_1$ can be solved using Padé tables. For instance, the 1985 paper A New Algorithm for Solving Toeplitz Systems of Equations by Frank de Hoog illustrates the solution.
I believe the 2017 paper could be incorrect in its assertion of $O(nlog(n))$ and it is in fact $O(nlog^2(n))$ due to the complexity of the Padé table based subproblems.