Defining the problem

In order to be able to apply any of the widely used search strategies we will be considering for use in the project, we will need to define some way of performing an ``incremental search'' on our problem. A search where we can take steps, and decide which way to go after every step. This is necessary in order to limit the size of the subspace we seek thru.

Now, what is our solution space ? It could be seen as many things. We could search in one space first, then in another, eg. ordering the rows first, then the columns and finally the rotation sequence. Or perhaps we should decide upon the rotation sequence first ?

Some time was spend in the very beginning of this project, experimenting with different strategies, and ways of searching. I came to several conclusions doing this:

1.

Attempting to find the optimal rotation sequence on a system is hard

2.

Until we have a complete ordering of the rows and columns, we can say little or nothing about an optimal rotation sequence

With this in mind, I decided upon the strategy that is used in the final optimizer.

The strategy is: First, decide which row should be the upper-most row, and which column should be the left-most column. Calculate or estimate the cost of this partial solution. Then, decide on the second-upper-most row, and the second-left-most column, calculate or estimate again, and so on. For each of these partial orderings, we find a suitable sequence of Givens Rotations in order to be able to estimate a lower bound on the cost of the current solution. More on this later.

As one notices, we do not at all consider the rotation sequence in this ordering strategy. In fact, the actual rotation sequence is found from a very simple algorithm, which has some roots in theory and some roots simply in experience gathered:

• We always use diagonal-elements for eliminating non-zeros below the diagonal.
• We eliminate non-zeros column-wise, from the left to the right.
• If there is more than one row with a non-zero in the current column, we choose the row with the smallest weighted sparsity distance to our row holding the diagonal-element.