AN ALGORITHM FOR SOLVING DISCRETE-TIME WIENER - HOPF EQUATIONS BASED UPON EUCLIDS 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 lambda such that M lambda equals 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. The algorithm gives a solution, if one exists, even when the Toeplitz matrix M is singular. It requires O (t**2 ) arithmetic operations for t unknowns, in the sense that the number of multiplications or divisions is directly proportional to t**2 . A faster algorithm is also presented based upon the half greatest common divisor algorithm; it requires O (t log**2 t) arithmetic operations.