A scalable parallel algorithm for periodic symmetric Toeplitz tridiagonal systems
Xian‐He Sun · 2001
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.