Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R to the end of the diagonal? As an example, consider the following snippet of MATLAB code:
A = [1 1 1; ... -1 -1 1; ... 0 0 -1; ... 0 0 1; ... -1 0 0; ... 0 -1 0]; s = [1e-8;1e-8;1e-8;1;1e-8;1]; B = sparse([A diag(s)]); [Q,R,p] = qr(sparse(B)'); pp = [5,6,1,2,4,3]; [QQ,RR] = qr(sparse(B(pp,:)'));
This matrix is similar to what may occur in an optimization problem with small slack variables. If we look at the absolute value of the diagonal elements of
R, we see a small element in position 5:
I would prefer this element to be at the end of the diagonal of
R. Using the permutation
pp, this can be achieved and the the diagonal of
RR is seen in this image:
In this case, the sparsity between
RR is the same. Ideally, I'd like a diagonal sorted by absolute value similar to what is achieved in a dense QR factorization. In that case, it's easy to get a rough idea of the effective rank of the original matrix and truncate the matrix
R effectively for the applications that I care about. At the same time, I understand that this would dramatically impact the sparsity of
R and for large matrices this is not tractable. In truth, I don't really need a fully sorted diagonal, but some kind of permutation that mostly puts the small elements at the end. At the moment, I have some very large matrices and may get some very small elements in the first few dozen diagonal elements, which is undesirable.
As some additional information, if it helps, I understand that MATLAB uses
spqr as its underlying QR factorization algorithm and that the parameter
spqrtol can be set in
spparms to adjust the drop tolerance for small elements. Alternatively, spqr could just be used directly. In this case, I'd contend the issue is how to effectively set this tolerance if the issue is small diagonal elements compared to other diagonal elements.
Thanks for any insights.