The Optimization

In short, we wish to find a row- and column ordering, and a sequence of Givens Rotations, that together will produce a QR factorization of our system of equations with a minimal computational cost.

Now, there are $(2n)!$ combinations of row- and column orderings, if our system has $n$ equations with $n$ unknowns. And if we have $k$ non-zeros in the system, we will need $\mathcal{O}(k)$ Givens Transforms, giving us $\mathcal{O}(k!)$ combinations there. All in all, we have $\mathcal{O}((2n)!k!)$ possible combinations. For the $56\times 56$ system with roughly 12% non-zeros, this amounts to a number of combinations in the order of $10^{185}$.

Clearly, exhaustive search thru the solution space is not an option. We will have to apply some strategy, in the hope that we can somewhat limit out search to some small number of small sub-spaces of the solution space.