Parallel QR Factorization Algorithm Using Local Pivoting

摘要

This reprint presents a new parallel version of the Householder algorithm with column pivoting for computing the QR factorization of a matrix. In contrast to the standard algorithm we employ a local pivoting scheme that allows for efficient implementation of the algorithm on a parallel machine, in particular one with a distributed architecture. An inexpensive but reliable incremental condition estimator is used to control the selection of pivot columns by obtaining cheap estimates for the smallest singular value of the currently created upper triangular matrix R. Numerical experiments show that the local pivoting strategy behaves about as well as the traditional global pivoting strategy. They also show the advantages of incorporating the controlled pivoting strategy into the traditional QR algorithm to guard against the known pathological cases. (kr)