A BINARY-TREE IMPLEMENTATION OF A PARALLEL DISTRIBUTED TRIDIAGONAL SOLVER

A divide-and-conquer algorithm for the resolution of distributed linea r tridiagonal systems of equations is implemented within a binary tree connection architecture. A new scheme for the distribution of the dat a among the computing nodes allows a dilation-one implementation of a recursive substitution scheme for the solution of the global system. I n this way, computation time decreases linearly with the number of nod es, and the data communication required becomes proportional to the lo garithm of the number of nodes. This takes place within a network with a fixed connectivity degree of three.