On the methods for solving Yule-Walker equations

The three well-known fast algorithms for the solution of Yule-Walker equations-the Levinson, Euclidean, and Berlekamp-Massey algorithms-are reviewed, and the relationship between each of them and the Pade approximation problem is shown. The algorithms are classified with reference to three criteria, namely: (1) the path they follow in the Pade table; (2) the organization of the computations (one-pass or two-pass); and (3) the auxiliary variables used. This classification shows that the set of known classical algorithms is not complete, and the missing variants are proposed. With these variants of the Berlekamp-Massey and Euclid algorithms, both forward and backward predictors can be obtained without additional cost. A unified representation of the two-pass algorithms is given in such a way that the application of the divide and conquer strategy becomes straightforward. A general doubling algorithm which represents all the associated doubling algorithms in an exhaustive way is provided