The computation and communication complexity of a parallel banded system solver

Abstract

We present an algorithm for solving banded positive defimte linear systems on a multiprocessor computer whose number of processors p is much less than the order of the system n. Assuming that the banded matrix, of bandwidth 2m + 1, is stored in the global memory by diagonals as several onedlmensmnal arrays, we consider the time required by several alignment networks for allocating the appropriate data to the local memory of each processor. We demonstrate that the time required in this preprocessmg stage does not exceed that required by the algorithm provided we use a shuffle exchange, a plpelmed shuffle exchange, or a crossbar switch. Once the data are allocated in the local memories, the algorithm requires only a "nearest neighbor" alignment network to achieve a total time of O(m'~n/p). The total cost of the algorithm is minimized when p ~ ~.