IMMITTANCE-TYPE 3-TERM SCHUR AND LEVINSON RECURSIONS FOR QUASI-TOEPLITZ COMPLEX HERMITIAN MATRICES

A comprehensive analysis is made of Schur- and Levinson-type algorithms for Toeplitz and quasi-Toeplitz matrices that have half the number of multiplications and the same number of additions as the classical algorithms. Several results of this type have appeared in the literature under the label "split algorithms." In this approach the reduction in computation is obtained by a two-step procedure: (i) the first step is a variable (or "recursion-type") transformation from the classical (i.e., "scattering") variables to a new (so-called, "immitance") set of variables, which by itself reduces the number of multiplications at the cost of increasing the number of additions; (ii) the second step achieves control of the number of additions by converting the two-term recursions into the lesser known (for discrete orthogonal polynomials) three-term recursions. In the Toeplitz case the new variables turn out to be the odd even parts of the classical variables, leading to the terminology of split algorithms, but this feature is lost in the quasi-Toeplitz case. Nevertheless, the network-theoretic interpretation of a transformation from scattering to immittance variables can still be maintained. Certain judicious choices of free parameters have to be made in each case in order to achieve the maximum computational reduction. It is shown how these results yield efficient procedures for determining the intertia of a quasi-Toeplitz matrix and the location of roots of its "predictor" polynomials from the immittance-type three-term recursions. In particular, connections with the Bistritz stability test, which was the motivation for our study of the Levinson and Schur algorithms in this paper, are noted.