The Heuristic

The heuristic that is used in the final optimizer, uses a fixed column ordering and orders the non-fixed rows to form a legal system. The cost of factorizing this resulting system is then used as the heuristic.

The non-fixed columns are ordered so that the columns with the most non-zeros are positioned right-most in the system. They are sorted so that the number of non-zeros are descending as we move to the left. This is not necessarily optimal, but it proves experimentally to be ``good''.

Ordering the rows, given the column-ordering, is done using bipartite matching. Any matrix holding some number of non-zeros can be seen as a bipartite graph. Finding a bipartite matching on this graph, will again yield an ordering of the rows guaranteeing non-zeros in all of the diagonal elements. This is illustrated in figure 3.2.

Figure 3.2: Matrix and bipartite graph before and after matching

$\parbox{4cm}{$ \left( \begin{array}{cccc} x & x & x & x \\ 0 & 0 & x & x \\ x & x & 0 & 0 \\ 0 & x & x & 0 \end{array} \right)$}$ $\parbox{3cm}{\includegraphics[height=2cm]{bipartite.eps}}$

$\parbox{4cm}{$ \left( \begin{array}{cccc} x & x & 0 & 0 \\ 0 & x & x & 0 \\ 0 & 0 & x & x \\ x & x & x & x \end{array} \right)$}$ $\parbox{3cm}{\includegraphics[height=2cm]{bipmatch.eps}}$

Luckily, bipartite matching runs in close-to $\mathcal{O}(n)$ time and memory, given $n$ columns and rows.

The drawback of bipartite matching is, that we do not necessarily find an ordering of the rows which is anywhere near optimal (wrt. minimizing fill-ins in the following QR factorization). However, this will prove to be of little importance. The quality of the ordering is still good enough, and the run-time efficiency seems to make it up for any extra branches descended due to the worse heuristic.