Strong Rank Revealing QR decomposition

A matlab implementation of the strong rank revealing QR.

This code is for the strong rank-revealing QR (Strong RRQR) introduced in the following reference.

Reference:

Gu, Ming, and Stanley C. Eisenstat. "Efficient algorithms for computing a strong rank-revealing QR factorization." SIAM Journal on Scientific Computing 17.4 (1996): 848-869.

Given a target matrix A, a strong RRQR of A is of form

AP = [Q1, Q2] * [R11, R12; 0 R22] \approx Q1 [R11, R12]

where P is a permutation matrix, [Q1,Q2] has orthonormal columns, and R11 is an upper-triangular matrix. R11 and R12 need to satisfy that matrix inv(R11)*R12 has each entry bounded by a pre-specified constant that is not less than 1.

The code contains the strong rank revealing QR with (1) a fixed rank, i.e., the dimension of R11; (2) an error threshold, i.e., each column of R22 has norm less than the threshold. The implementation strictly follows the algorithms proposed in the above reference.

Note:

The main time-consuming step in the code is usually a complete pivoting QR decomposition of the target matrix A, i.e. [Q,R,p] = qr(A, 0). Practically, the algorithm only requires a partial pivoting QR (R22 doesn't have to be upper-triangular) but I can't find an efficient partial pivoting QR implementation. Greatly appreciated if any one can provide an efficient partial pivoting QR code for both a fixed rank or a fixed threshold.