A PARALLEL SOLVER FOR CERTAIN CYCLIC TRIDIAGONAL TOEPLITZ SYSTEMS ON DISTRIBUTED MEMORY MULTICOMPUTERS

A parallel algorithm for certain cyclic tridiagonal Toeplitz systems on distributed memory multicomputers is presented. This kind of cyclic tridiagonal Toeplitz systems occurs repeatedly in the solution of implicit finite difference equations derived from linear first order hyperbolic equations, i.e. the transport equation, under a variety of boundary conditions. The algorithm is based on the factorization of the coefficient matrix and the principle of “divide and conquer” in designing parallel algorithms. Full use is made of the special structure of the coefficient matrix. There is less redundancy computation caused by parallelization. The communication mechanism is simple. The algorithm is stable and its parallel efficiency is high. The analysis of complexity and numerical experiments shows that the algorithm’s speedup satisfy S p（n）→p（n→+∞） . This is the best result a parallel algorithm can reach. The results of numerical experiments about the algorithm on a distributed memory multicomputer are also given.