With parallel algorithm solved tridiagonal system

Abstract

In recent years there has been increasing in-terest in the study and research of parallel algorithms. Parallel programming uses multiple computers or dis-tributed computing system to solve the problem at simul-taneous and computational speed is faster than a single computer. This paper utilized divide-and-conquer concept to present brand-new method of parallel process in order to solve tridiagonal system. This skill is called “Recur-sive-Doubling-Elimination” algorithm. This approach al-lows a tridiagonal system to be solved in O(log2 n) times on a barrel shifter network of O(n/log2 n) processors. It is also cost-optimal in the sense that the product of the exe-cution time and the number of processors is minimal.