The double-diagonal system

Having seen the impacts of optimization on systems of randomly distributed non-zeros, it is also interesting to look at optimization of not-so-randomly distributed non-zero systems. Two different systems will be considered here. The first one is a system with two diagonals, one from the upper-left to the lower-right corner, and one orthogonal to this. If one thinks about how this could possibly be optimized, one may realize the interesting property of this system: It is not possible to simply move non-zeros from below the main diagonal, without moving another non-zero below it again. The system is shown in figure 7.5.

Figure 7.5: The double-diagonal system. $ns=14.80\%$

This system is the last in the series of hardly-improving systems. Because of the ugly property, that we cannot relocate any of the other-diagonal non-zeros to above the first diagonal, without relocating a non-zero below that diagonal too, we shouldn't expect too much of an optimization. As seen in figure 7.6, the optimization didn't yield much of an improvement. Although the R matrix is still somewhat sparse, the original structure of the system is a ``QR-killer''. This system demonstrates very well, that although a system may be sparse, it is not necessarily well suited at all, for QR factorization. Not even when put thru the optimizer.

Figure 7.6: Ordered ``double-diagonal'' system before and after QR

Solver	KFLOPS
MatLab	313.6
QR	160.6