A parallel algorithm for solving tridiagonal linear systems on coarse grained multicomputer - Saukas, E. L. G.; Song, S. W. (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD); 1997: Anais do IX Simpósio Brasileiro de Arquitetura de Computadores e Processamento de Alto DesempenhoDO - 10.5753/sbac-pad.1997.22642, 1997)
The CGM (coarse-grained multicomputer) model has been proposed to be a model of parallelism sufficiently close to existing parallel machines. Despite its simplicity it intends to give a reasonable prediction of performance when parallel algorithms are implemented. Under the CGM model we design a communication-efficient parallel algorithm for the solution of tridiagonallinear systems with n equations and n unknowns. This algorithm requires only a constant number of communication rounds. The amount of data transmitted in each communication round is proportional to the number of processors and independent of n. In addition to showing its theoretical complexity, we have implemented this algorithm on a real distributed memory parallel machine. The results obtained are very promising and show an almost linear speedup for large n indicating the efficiency and scalability of the proposed algorithm.