A parallel algorithm to solve symmetric tridiagonal linear systems

For linear systems with coefficient matrices of classical structure, WZ factorizations for matrices are basic mathematical theories to design a class of parallel algorithms. Based on WZ factorization, a parallel algorithm is provided for symmetric tridiagonal linear systems. The method estimates the computation task carefully so that it assigns the system skillfully to get even load balance. In addition, the algorithm makes full use of the overlap between computation and communication to reduce waiting time in each processor. Both the subsystem assigned in each processor and the reduced subsystem have the same computing logic, as a result, a two-level method forms. By theory analysis and experiment results, it can be concluded that our method is effective in load balance and efficiency.