Vectorized Parallel Solver for Tridiagonal Toeplitz Systems of Linear Equations

摘要

The aim of this paper is to present two versions of a new divide and conquer parallel algorithm for solving tridiagonal Toeplitz systems of linear equations. Our new approach is based on a recently developed algorithm for solving linear recurrence systems. We discuss how to reduce the number of necessary synchronizations and show proper data layout that allows to use cache memory and SIMD extensions of modern processors. Numerical experiments show that our new implementations achieve very good seedup on multicore and manycore architectures. Moreover, they are more energy efficient than a simple sequential algorithm.