The upper-triangular system

The title of this section is somewhat misleading. This system does indeed have an upper-triangular structure, but unlike the usual upper-triangle, this upper triangle is located in the upper left corner of the system. Thinking of the way QR works, this system seems unsuitable for QR factorization, at least if the rows and columns are not re-ordered. Fortunately, the high concentration of non-zeros in one isolated part of the system poses good opportunities for relocating these non-zeros to somewhere else, where their impact on the total cost of the solution will not be so severe. The system can be seen in figure 7.7.

Figure 7.7: The alternative upper-triangular system. $nz = 17.38\%$

As expected, this system did benefit from the optimization. It is clearly seen in figure 7.8, that the high concentration of non-zeros in the most unfortunate (from a QR point of view) position in the upper left corner, has been relocated to positions mostly above the diagonal, and the ones which are below the diagonal are located near the very bottom of the system, to minimize their impact on the rows below them (by minimizing the number of rows below). The R matrix is fairly dense though. This implies, that the back-substitution will be fairly expensive, comparable to back substitution on a dense system. The QR factorization however, will be fairly cheap (again compared to a dense factorization), because of the large number of non-zeros below the diagonal.

Figure 7.8: Ordered ``upper triangular'' system before and after QR

Solver	KFLOPS
MatLab	357.0
QR	146.2