1997 | OriginalPaper | Chapter
Parallel Algorithms for Computing Rank-Revealing QR Factorizations
Authors : Gregorio Quintana-Ortí, Enrique S. Quintana-Ortí
Published in: Workshop on High Performance Computing and Gigabit Local Area Networks
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The solution to many scientific and engineering problems requires the determination of the numerical rank of matrices. We present new parallel algorithms for computing rank-revealing QR (RRQR) factorizations of dense matrices on multicomputers, based on a serial approach developed by C. H. Bischof and G. Quintana-Ortí. The parallel implementations include the usual QR factorization with column pivoting, and a new faster approach that consists of two stages: a QR factorization with local column pivoting and a reliable rank-revealing algorithm appropriate for triangular matrices. Our parallel implementations include the BLAS-2 and BLAS-3 QR factorizations without pivoting since they are a good reference point, though they are not appropriate for rank-revealing purposes.Experimental comparison shows considerable performance improvements of our new approach over classical rank-revealing algorithms on the platforms we used: an IBM SP2 platform and a cluster of SGI workstations.We study the effect of the computer communication network and the processor computational power on the performance of the algorithms. In this case, as well as in many other parallel and distributed applications, the latency and bandwidth of the network are much more important than the processor computational power and, thus, these are the key factors impacting performance.