An efficient algorithm for a large Toeplitz set of linear equations

Abstract

An algorithm is presented which requires <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2n^{2} + 8n \log_{2} n - n</tex> computations for solving a set of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> linear Toeplitz equations for n = 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> , where k is a positive integer. The previously known algorithms require a minimum of 3n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">6n \log_{2} n + 3n</tex> computations.