Fast inversion of banded Toeplitz matrices by circular decompositions

Banded Toeplitz matrices of large size occur in many practical problems [1]-[6]. Here the problem of inversion as well as the problem of solving simultaneous equations of the type Hx = y, when H is a large banded Toeplitz matrix, are considered. It is shown via certain circular decompositions of H that such equations may be exactly solved in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(N log₂ N)</tex> rather than in O(N 2 ) computations as in Levinson-Trench algorithms. Furthermore, the algorithms of this paper are nonrecursive (as compared to the Levinson-Trench algorithms), and afford parallel processor architectures and others such as transversal filters [17] where the computation time becomes proportional to N rather than to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N log N</tex> . Finally, a principle of matrix decomposition for fast inversion of matrices is introduced as a generalization of the philosophy of this paper.