Fast direct solution methods for symmetric banded Toeplitz systems, based on the sine transform

AbstractWe present new fast direct methods for solving a large symmetric banded Toeplitz system of order n with bandwidth p. We make use of structured matrices which can be diagonalized by the discrete sine transform matrix, sometimes called τ-matrices. A first method writes the Toeplitz matrix as the sum of a τ-matrix and a low rank matrix. A second method embeds the Toeplitz matrix in a larger τ-matrix of order m. The methods are similar to Jain [IEEE Trans. Acoust. Speech Signal Process. 26 (1978) 121] and Linzer [Linear Algebra Appl. 170 (1992) 1], who worked with circulant matrices. Both algorithms consist in solving two τ-systems and two smaller systems. A τ-system of order n can be solved in O(nlogn) by using a discrete sine transform if n+1 has small prime factors. Therefore, the second algorithm is preferable, since we can choose m such that m+1 has small prime factors. On the other hand, in the second method the smaller systems can become large when m differs too much from n, while in the first method the order is always p−1. In both methods, the small systems have low displacement rank, so we can use fast methods to solve them