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 O (N ₂ N) 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 N N. Finally, a principle of matrix decomposition for fast inversion of matrices is introduced as a generalization of the philosophy of this paper.