An algorithm for solving discrete-time Wiener-Hopf equations based upon Euclid's algorithm

An algorithm for solving a discrete-time Wiener-Hopf equation is presented based upon Euclid's algorithm. The discrete-time Wiener-Hopf equation is a system of linear inhomogeneous equations with a given Toeplitz matrix M, a given vector b, and an unknown vector thatMλ = b. The algorithm is able to find a solution of the discrete-time Wiener-Hopf equation for any type of Toeplitz matrices except for the all-zero matrix, while the Levinson algorithm and the Trench algorithm are not available when at least one of the principal submatrices of the Toeplitz matrixMis singular. The algorithm gives a solution, if one exists, even when the Toeplitz matrixMis singular, while the Brent-Gustavson-Yun algorithm only states that the Toeplitz matrixMis singular. The algorithm requiresO(t²)arithmetic operations fortunknowns, in the sense that the number of multiplications or divisions is directly proportional tot², like the Levinson and Trench algorithms. Furthermore, a faster algorithm is also presented based upon the half greatest common divisor algorithm, and hence it requiresO(t log² t)arithmetic operations, like the Brent-Gustavson-Yun algorithm.