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].

Thu Sep 18 20:40:30 CDT 1997