ON THE PARALLEL SOLUTION OF TRIDIAGONAL SYSTEMS BY WRAP-AROUND PARTITIONING AND INCOMPLETE LU FACTORIZATION

Two methods are presented which efficiently solve tridiagonal systems on vector supercomputers and parallel computers with a moderate degree of parallelism. The first algorithm for diagonally dominant systems uses incomplete Gaussian elimination, the other for more general systems applies Gaussian elimination with partial pivoting. The methods are based on wrap-around partitioning, which is closely related to the partitioning used in Wang's algorithm. The first algorithm delivers an asymptotic speedup by a factor of p on a p-processor computer if compared to the scalar algorithm, whereas the second algorithm delivers a speedup by a factor of roughly p/2, which is also typical for cyclic reduction. For the incomplete factorization, existence and approximation properties are proved. Timing experiments were run on a Cray X-MP.