QR factorization for shared memory and message passing

This paper describes the design, implementation, and performance of three new parallel QR factorization algorithms: shared memory, synchronous message passing, and asynchronous message passing. In contrast to existing parallel algorithms, the multiprocessor partitioning strategy is not governed by an underlying static data distribution scheme. Rather, a dynamic distribution strategy is employed to improve scalability on small problems. Experiments conducted on a 128-processor SGI Origin 2000 and a 64-processor HP SPP-2000 show that the new algorithms have a lower execution time than available tuned parallel routines installed on the machines including a version of ScaLAPACK's distributed QR factorization algorithm PDGEQRF. (C) 2002 Elsevier Science B.V. All rights reserved.