×

A parallel algorithm for solving tridiagonal linear systems. (English) Zbl 1196.65063

Summary: The coarse-grained architecture model has been proposed to be a model, of parallelism sufficiently close existing parallel machines. Under this model, we design a communication-efficient parallel algorithm for the solution of tridiagonal linear 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.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation
65Y10 Numerical algorithms for specific classes of architectures
PDFBibTeX XMLCite