Sparse Multifrontal Rank Revealing QR Factorization

We describe an algorithm to compute an approximate rank revealing sparse QR factorization. We use a two phase algorithm to provide especially high accuracy in the labeling of some columns as ``redundant,' which ensures robustness in the use of our factorization in computing explicit bases of the nullspace. Our first phase is similar in outline to other proposed sparse RRQR factorizations, in that we couple a standard sparse QR factorization scheme with a condition estimator to develop a factorization with a well-conditioned leading block. There are important details in our implementation of the condition estimator and pivoting that enhance efficiency and reliability. However, the exceptional characteristic of our algorithm is its second phase, which ensures that columns labeled as redundant lead to highly accurate nullvectors. The second phase requires that we compute all columns of R explicitly in the first phase; we cannot discard ``redundant' columns as is often done elsewhere. This condition, in the presence of pivoting to reveal the rank, requires dynamic data structures and necessarily degrades sparsity. But the additional work fits naturally into the multifrontal factorization's use of efficient dense vector kernels, minimizing overall cost. We present a theoretical analysis that shows that our use of approximate singular vectors does not degrade the quality of our rank-revealing factorization; we achieve an exponential bound like methods that use exact singular vectors. We provide results of numerical experiments and close with a discussion of limitations of this approach.