EFFICIENT ALGORITHM FOR A LARGE TOEPLITZ SET OF LINEAR-EQUATIONS

An algorithm is presented which requires 2n2 + 8n log2 n − n computations for solving a set of n linear Toeplitz equations for n = 2k, where k is a positive integer. The previously known algorithms require a minimum of computations. The major advantage of the algorithm is realized for those applications where the set of n Toeplitz equations Tx = c is to be solved for a different c and the same T for the unknown x. Each additional solution requires storing only (4n + 1) elements from the first solution and 6n log2 n + 3n computations. © 1979 IEEE