Computational costs

Obviously we are not very keen of the thought of using trigonometric functions throughout the factorization. Fortunately, there exists an efficient formula for calculating the rotation coefficients $c$ and $s$ from above. The following is taken from [MC]. If we want to eliminate element $b$ using element $a$, assuming both are non-zero, the coefficients are given by:

$$\vert b\vert \geq \vert a\vert : \tau = -a/b;\quad s=1/\sqrt{1+\tau^2};\quad c=s\tau$$ (2.3)

$$\vert b\vert \leq \vert a\vert : \tau = -b/a;\quad c=1/\sqrt{1+\tau^2};\quad s=c\tau.$$ (2.4)

This formula costs us 5 FLOPS plus a square-root. (For the pedantic, it should be mentioned, that the case $\vert a\vert=\vert b\vert$ will probably never occur, and which one of the two formulas above are used in this case does not matter).

The actual rotation of two rows, given by repeating equation 2.1, will cost us $6p+2q$ FLOPS, if $p$ is the number of elements in the rows rotated where both rows have non-zeros, and $q$ is the number of elements where only one row has a non-zero.

Finally, the back-substitution of one row costs us approximately $2p+2$ FLOPS, where $p$ is the number of non-zeros in the row currently being worked on.

Depending on the hardware on which we run the actual factorization, the square root used in equations 2.3 and 2.4, can cost anything from one FLOP to ``many'' FLOPS. We take the liberty to account one FLOP for every square-root used, but this is easily changed in the actual optimizer.

<