Linear algebra and its applications vol:343 pages:211-232
We 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 tau-matrices. A first method writes the Toeplitz matrix as the sum of a tau-matrix and a low rank matrix. A second method embeds the Toeplitz matrix in a larger tau-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 tau-systems and two smaller systems. A tau-system of order n can be solved in O(n log n) 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 + I 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. (C) 2002 Elsevier Science Inc. All rights reserved.