An Introduction to the Class of Split Levinson Algorithms

The split Levinson algorithms constitute a new class of efficient procedures to solve a linear system of equations exhibiting the positive definite Toeplitz structure. They can be derived from the classical Levinson algorithm by a kind of splitting operation, which results in a more efficient algorithm processing some well-defined symmetric polynomials (with complex coefficients). The algorithm thus obtained is based on a simple two-step recurrence relation satisfied by these polynomials. The paper provides a self-contained introduction to the whole class of split Levinson algorithms, including a detailed technical derivation. This class is shown to depend on two unit modulus parameters, which can be chosen at will by the user.