A storage-efficient method for solving banded Toeplitz systems

摘要

A method is presented for solving the banded Toeplitz system Tx=y by decomposing T into its asymptotic upper and lower triangular factors (which are banded and Toeplitz) and a rank-p correction matrix, where p is the bandwidth of T. This way of representing T requires only O(p/sup 2/) words of storage and allows computation of x in O(2Np) operations. A similar method is presented for the case in which T is bi-infinite and y is zero outside a finite region.