Fast least squares algorithm based on partitioning technique

A new approach is presented for solving least squares (LS) problems. It allows a much higher multiprocessor efficiency, compared to the conventional method, when implemented on a distributed memory parallel processor (DMPP) architecture. The conventional method of Gram-Schmidt (GS) factorization gives very poor multiprocessor efficiencies on DMPP architectures, because the concerned computational process is inherently sequential. However, the proposed approach partitions the given data matrices/vectors with a desired partitioning factor s. As far as the required number of computations for the proposed method are concerned, two observations are made. First, the total computational complexity is either nearly equal to or less than that corresponding to the conventional method. Second, the proposed method achieves substantial improvement in the degree of parallelism