next up previous
Next: The Generalized Schur Up: Classical Foundations of Algorithms Previous: The Szego Recursions

Toeplitz Inversion Formulas

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



next up previous
Next: The Generalized Schur Up: Classical Foundations of Algorithms Previous: The Szego Recursions



Greg Ammar
Thu Sep 18 20:40:30 CDT 1997