Direct Toeplitz solvers can be divided into two phases: a
factorization or decomposition phase and a solution phase.
Toeplitz solvers that rely on triangular
factorizations of M or of 
require 
flops in the first phase to compute the factorization, and
an additional 
flops in the second phase
to use the factorization to solve Mx=b. However, several formulas
exist for expressing 
in terms of its last column (or equivalently,
in terms of 
and 
) which can provide
for increased efficiency in the second phase of a Toeplitz solver.
These Toeplitz inversion formulas also follow directly from results
of Szego.
The reproducing kernel polynomial 
of degree n associated with the inner product defined by 
is given by
Szego proved the following identity:
See [36, § 11.4,] or [25, § 2.3,].
The kernel
polynomial is therefore determined by the Szego polynomial of
degree n and its squared norm 
.
This formula
is analogous to the Christoffel-Darboux formula for polynomials
that satisfy a Jacobi-type three-term recurrence relation
[36,1].
By comparing (5.1) and (4.5), we see that
the coefficient of 
in
is the 
entry
of 
.
Consequently,
Szego's formula (5.2)
allows
one to construct 
from the coefficients of
the last Szego polynomial 
and its squared norm
.
This was first observed by Trench [37], who
presented an algorithm for constructing 
using 
operations. See [10,24] for concise
descriptions of Trench's algorithm.
If we view the polynomials in Szego's formula (5.2) in terms
of the corresponding triangular Toeplitz matrices, we obtain
a decomposition of 
called the
Gohberg-Semencul formula.
Specifically, let 
, with 
,
denote the vector containing the coefficients of the monic Szego polynomial
, and let
denote the lower triangular Toeplitz matrix whose first
column is 
. Also let 
and
denote the downshift matrix
and the reversal matrix, respectively, where
is the identity matrix of order n+1.
Then the vectors 
and 
correspond to 
and 
,
respectively, and we obtain from (5.2)
the Gohberg-Semencul formula for 
,
This formula is actually one of several formulas introduced by Gohberg and Semencul that express the inverse of a Toeplitz matrix as the difference of products of triangular Toeplitz matrices [23,26]. These formulas have had a significant impact in computational and theoretical problems involving Toeplitz matrices, and in generalizing algorithms for Toeplitz matrices to larger classes of matrices. One notable area of research stimulated by the Gohberg-Semencul formulas is the work on displacement structures of matrices, beginning with [30,18]. These ideas have proved to be powerful in generalizing the Gohberg-Semencul formula and algorithms for Toeplitz equations to larger classes of matrices. See, for example, [32,19,29] as well as the recent survey [31] and references therein.
The utility of the Gohberg-Semencul formula in the solution of
Toeplitz equations stems from the fact that it can be used
to compute 
using fast Fourier transform (FFT) techniques
in 
arithmetic operations [27].
This is especially advantageous when several systems of equations
involving the same Toeplitz matrix are to be solved, since the first
phase of the Toeplitz solver, which involves a higher order amount
of computation, would be performed only once.
Toeplitz inversion formulas that provide for increased computational efficiency in the second phase of a Toeplitz solver are presented in [3,2], in which triangular Toeplitz matrices in (5.3) are replaced with circulant and skew-circulant matrices determined by the vector r. These formulas were derived using ideas of cyclic displacement from [19], but they can also be derived directly from the Gohberg-Semencul formula. The formula involving circulant and skew-circulant matrices presented in [2] provides computational savings of over 42 percent relative to the use of the Gohberg-Semencul formula in the second phase of a Toeplitz solver. Since then there have been several other formulas presented that achieve this same level of efficiency in multiplying a vector by the inverse of a Toeplitz matrix, and also generalize to a variety of other matrix structures [22,12,16,13].
