QR Factorization for Linear Least-Squares Problems on a Hypercube Multiprocessor

Least squares problems occur in many branches of science. Typically there may be a large number of data points or observations and only a small to moderate number of variables. On sequential machines these problems can be time-consuming and therefore the use of parallel machines to solve large least-squares problems may well yield substantial savings. The solution of least-squares problems by a QR factorization using Givens rotations seems to be particularly suitable for a parallel machine, because there is much choice in the order of the Givens rotations and many Givens rotations can be carried out in parallel. In this paper, an implementation of a QR factorization on the Intel ' hypercube is described. Each row of the least-squares matrix is assigned to a processor and most of the rotations involve rows within one processor in the usual case when each processor receives several rows. However, it is also necessary to carry out rotations involving rows in different processors and we call these rotations merges. Two ways of implementing the merges are described and they are compared on the grounds of load balance and the number of communications required. One feature of the implementations is that processors can continue to do Givens rotations on rows within the processor while waiting for messages that are required for merges. There is also some flexibility in the order of the merges and this can be incorporated into the algorithm. For each column, the merges are carried out according to a tree structure and the choices of trees and their roots are discussed. Numerical results are given to show the usefulness and efficiency of the proposed algorithms