مرکز منطقه ای اطلاع رساني علوم و فناوري - An algorithm for solving discrete-time Wiener-Hopf equations based upon Euclid´s algorithm

Abstract :

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 $\\lambda$ such that $M\\lambda = 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 matrix $M$ is singular. The algorithm gives a solution, if one exists, even when the Toeplitz matrix $M$ is singular, while the Brent-Gustavson-Yun algorithm only states that the Toeplitz matrix $M$ is singular. The algorithm 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}$ , like the Levinson and Trench algorithms. Furthermore, a faster algorithm is also presented based upon the half greatest common divisor algorithm, and hence it requires $O(t \\log ^{2} t)$ arithmetic operations, like the Brent-Gustavson-Yun algorithm.