A fast modified sine transform for solving block-tridiagonal systems with Toeplitz blocks

In this report we consider block-tridiagonal systems with Toeplitz blocks. Each block is of sizen×n consisting ofn_c×n_c matrices as entries, and there arem×m blocks in the system. The solution of those systems consists of 2n_cm modified sine transforms and an intermediate solution ofn block-tridiagonal systems. Symmetries in the data vectors are exploited such that one modified sine transform can be computed in terms of one Fourier transform of half the length of the original one, hence requiringO(2.5nlog₂n) operations. Similarly, we only have to solve (n+1)/2 of the intermediate systems due to symmetry.This work was supported by the Swedish National Board for Industrial and Technical Development, NUTEK, under contract No. 89-02539 P.