For the triangular Sylvester paper of 2003, is there any motivation for producing 16 different algorithms?

[wlad wladsnotmyrealname]

Quintana-Ortí, Enrique S.; van de Geijn, Robert A. (2003). Formal derivation of algorithms. ACM Transactions on Mathematical Software, 29(2), 218–243. doi:10.1145/779359.779365 

I've given the name and the title of the paper above. The paper mentions FLAME.

I think I understand how the 16 algorithms are derived. One of those algorithms is labelled C1 or "lazy", and appears to be the simplest one. Is there any use-case for the other 15? Is there any motivation for considering another 15 possibilities?

To me, it also seems that the 16 algorithms are all fairly similar to each other.

Thanks.

[wlad wladsnotmyrealname]

I think a similar result could be obtained by combining:

- Block matrices

- Structural recursion

- "Tail recursion modulo cons"

The last turns the recursion into a "while" loop. This should at least derive C1, or the "lazy" algorithm.

I think some of the C2-C16 variants can be obtained by moving stuff from the end of the while loop to its beginning.

I'm still wondering why these 15 other variants might be useful. Is caching the reason?

To explain my interests: I'm interested in very general methods for deriving numerical linear algebra algorithms.

[wlad wladsnotmyrealname]

> I think some of the C2-C16 variants can be obtained by moving stuff from the end of the while loop to its beginning.

I've realised these variants are *not* just the "lazy" algorithm (or C1) with the body of the while-loop rearranged.

If that were the case, it would contradict the fact that -- looking at the loop invariants -- each iteration of the loop

modifies the matrix globally, instead of just some bottom-left portion of it.