Fast inversion of banded Toeplitz matrices by circular decompositions
A. Jain · IEEE Transactions on Acoustics Speech and Signal Processing · 1978
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 inO(N \log_{2} N)rather than in O(N2) 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 toN \log N. Finally, a principle of matrix decomposition for fast inversion of matrices is introduced as a generalization of the philosophy of this paper.