| Home > Publications > Reports > Numerical Analysis and Applied Mathematics (TW) |
TW 316
J. Hendrickx, M. Van Barel
Fast direct solution methods for symmetric band Toeplitz systems, based on the sine transform
Abstract
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 t-matrices. A first method writes the Toeplitz matrix as the sum of a t-matrix and a low rank matrix. A second method embeds the Toeplitz matrix in a larger t-matrix of order m. The methods are similar to Jain [A.K. Jain. IEEE Trans. Acoust. Speech Signal Process., 26: 121-126, 1978] and Linzer [E. Linzer. Linear Algebra Appl., 170:1-32, 1992], who worked with circulant matrices. Both algorithms consist in solving two t-systems and two smaller systems. A t-system of order n can be solved in O(n log n) flops 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.
report.pdf / mailto: J. Hendrickx