Title: Fast direct solution methods for symmetric banded Toeplitz systems, based on the sine transform
Authors: Hendrickx, Jef ×
Van Barel, Marc #
Issue Date: Mar-2002
Publisher: Elsevier science inc
Series Title: Linear algebra and its applications vol:343 pages:211-232
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 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.
ISSN: 0024-3795
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Numerical Analysis and Applied Mathematics Section
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science