[dvdhsu]

> This has 3 multiplications and 4 additions. We've saved 1 multiplication at the expense of 3 extra additions.

Stratssen's algorithm, for multiplying matrices, uses a similar "trick". Naive matrix multiplication uses 8 steps for a (2x2) * (2x2), or n^3 multiplications. Stratssen's lowers this to 7 multiplications, and instead uses extra additions, thus achieving O(N^~2.807).

http://en.wikipedia.org/wiki/Strassen_algorithm

[psykotic]

Yeah. There should be a similar conceptual explanation for Strassen's algorithm, but I haven't seen one. The 2x2 block matrix decomposition corresponds to viewing a (2n)x(2n) matrix as a 2x2 matrix over the ring of nxn matrices. There isn't any notion of evaluation for a 2x2 matrix ring, but we might look for other natural ring homomorphisms. The determinant and trace seem like obvious candidates. Unfortunately, the determinant respects multiplication but not addition, and the trace respects addition but not multiplication. Any ideas?

Edit: I've asked djb and we'll see if he responds.