A class of novel parallel algorithms for the solution of tridiagonal systems

In this paper, a new class of parallel Gaussian elimination algorithms is presented for the solution of tridiagonal matrix systems. The new algorithms, called ACER (alternating cyclic elimination and reduction), combine the advantages of the well known cyclic elimination algorithm (which is fast) and the cyclic reduction algorithms (which requires fewer operations). The ACER algorithms are developed with the unifying graph model.