I have the problem of solving very large and very sparse least squares problems and, a bit dissatisfied with the run-times of the full-fledged QR-algorithm, I would like to bring the instances into block upper-triangular shape to be able to apply some generalized form of back-substitution (here the horizontal and the vertical side of the triangle have different length).
The generalized back-substitution would then start by solving the least squares problem that corresponds to the lowest right block and then proceed upwards, solving the least squares problem of the next higher block after substituting already determined variables.
I'm not sure, whether that idea is of any benefit, but out of curiosity I would like to know, if there is a good strategy for matrix reordering (i.e. row- and column permutations) that brings a matrix into block upper-triangular shape by only evaluating the matrix entries itself.
this question is related to Showing block diagonal structure of matrix by reordering, but it is not quite the same and the solution given there is based eigenvalues, which is not what I want to evaluate.
A problem, where Least Squares Problems with such a Block structure naturally appear, is the numerical inversion of Radon Transforms; here the variables correspond to pixels and equations to lines and the non-zero entries correspond to intersected pixels.
Lines, that go through pixels near the center of the transformed region also pass through pixels near the periphery of that region. The block structure thus resembles certain anuli of pixels.