Parallel QR Method Using Fast Givens' Rotations

摘要

Given a prescribed order in which to introduce zeroes, and constraints on the architecture it is shown how to develop a parallel QR factorization based on fast Givens' rotations for a rectangular array of processors, suitable to VLSI implementation. Unlike designs based on standard Givens' transformations, the present one requires no square root computations. Assuming each processor performs the elementary operations (+,*,/), less than O(w sub 2) processors can achieve the decomposition of a w-banded, order n matrix in time O(n). Application is made to a variant of Bareiss' G-Algorithm for the solution of weighted multiple linear least squares problems. Given k different right hand side vectors, (w sub 2) processors compute the factorization in O(n + k) steps. (Author)