A Scalable Parallel Algorithm for Periodic Symmetric Toeplitz Tridiagonal Systems
Authors: X.-H. Sun
Date: January, 2001
Venue: International Journal of Computer Research, Vol. 10, No. 1, 2001, pp. 89-98.
Type: Journal
Abstract
Symmetric Toeplitz tridiagonal systems arise in many scientific applications. An efficient algorithm, the Simple Parallel Prefix (SPP) algorithm, was previously proposed for solving symmetric Toeplitz tridiagonal systems on SIMD and vector computers. Based on the SPP algorithm, a scalable parallel algorithm is proposed for solving periodic symmetric Toeplitz tridiagonal systems in this study. The newly proposed algorithm has the same parallel computation count as that of the SPP algorithm for non-periodic systems, and it requires only shift communication.