next up previous
Next: Schur's Algorithm and Up: Classical Foundations of Algorithms Previous: Classical Foundations of Algorithms

Introduction

Problems related to solving the system of equations Mx=b, where

is a Hermitian positive definite Toeplitz matrix, arise in several fundamental problems of signal processing, time series analysis, and image processing. There has therefore been a significant amount of effort devoted to developing efficient algorithms for solving positive definite Toeplitz equations. We refer to any of these algorithms as a Toeplitz solver.

The development of Toeplitz solvers goes back to the work of Levinson [33] in 1947, who presented a fast algorithm for solving a positive definite Toeplitz system of equations for solving discrete-time Wiener filtering problems. This work and subsequent work by Durbin [17] for solving the Yule-Walker equations of prediction theory, Trench [37] for constructing from the solution of one set of Yule-Walker equations, and Bareiss [8] for computing a triangular factorization of M form the foundation for direct algorithms for Toeplitz equations.

Toeplitz solvers can be divided into two classes: direct methods and iterative methods. The direct methods are further classified according to their arithmetic complexity. We will say that an algorithm that requires floating-point arithmetic operations (flops) is a fast algorithm. This is in contrast with the flops required by algorithms for arbitrary positive definite matrices, such as Cholesky's method. We will also refer to a method that requires flops as a superfast algorithm. While any superfast algorithm will require fewer flops than a fast algorithm for sufficiently large n, the practical value of a superfast algorithm will depend on when this crossover of flop counts is achieved, and also on the tractability of implementing the algorithm on a computer.

In this paper we give an overview of several direct Toeplitz solvers and their connections with Schur functions and Szego polynomials. Although knowledge of the connections with the classical theory is not necessary to derive the algorithms, we find the connections illuminating on the overall mathematical structure of the problems being considered. In fact, we have found the classical connections invaluable in understanding and implementing the superfast Toeplitz solver described in [5,6].



next up previous
Next: Schur's Algorithm and Up: Classical Foundations of Algorithms Previous: Classical Foundations of Algorithms



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