An efficient algorithm for a large Toeplitz set of linear equations
Jaswant R. Jain · IEEE Transactions on Acoustics Speech and Signal Processing · 1979
An algorithm is presented which requires2n^{2} + 8n \log_{2} n - ncomputations for solving a set ofnlinear Toeplitz equations for n = 2k, where k is a positive integer. The previously known algorithms require a minimum of 3n2computations. 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 and6n \log_{2} n + 3ncomputations.