A balanced submatrix merging algorithm for multiprocessor architectures

In this article, a parallel algorithm which applies Givens rotations to selectively annihilate k(k + 1)/2 nonzero elements from two k x n(k not more than n) upper trapezoidal submatrices is described. The new algorithm is suitable for implementation on either a pair of directly connected local-memory processors or two clusters of multiple tightly-coupled processors. Analyses show that in both cases the proposed algorithms achieve optimal speed-up by balancing the work load distribution and masking interprocessor or intercluster communication by computation if k is much small than n. In the context of solving large scale least squares problems, this submatrix merging step is repetitively needed during the entire computation and, furthermore, there are usually many pairs of such submatrices to be merged with each submatrix stored in the memory of a processor or a cluster of processors. The proposed algorithm can be applied to each pair of submatrices concurrently, and thus parallelizes an important step in solving the least squares problems.