4 ms·
what, no, you have this all wrong. the complexity of multiplying two 4x4 matrices is clearly constant. the important thing about the constant, however, is that
by pxx 4y ago
what, no, you have this all wrong. the complexity of multiplying two 4x4 matrices is clearly constant. the important thing about the constant, however, is that you can use this primitive on the block matrices recursively to possibly improve the asymptotic complexity.
the complexity improvement in this paper is for arithmetic in Z_2 (modular arithmetic over single bits). in standard arithmetic, there is no asymptotic complexity improvement but the developed algorithms involve more efficiently fusible[0] operations, which is useful for the target hardware.
[0] ed: this used to read 'with fewer multiplications,' which is clearly wrong: fewer multiplications would lower complexity. Interestingly, the discovered algorithm seems to have a larger number of additions, but still runs faster.
- boole1854 4y agoYou are correct. I will edit.
- a-dub 4y agoif you're in gf2 on a traditional cpu and care about wall clock time, i start to wonder how something like simd xors and parity would compare...
- ColinWright 4y agoI thought that savings on the number of multiplications leads to savings in complexity. For example, multiplying 2x2 matrices using 7 multiplications instead of 8 gives an improvement in complexity. See my comment here: https://news.ycombinator.com/item?id=33098192 https://news.ycombinator.com/item?id=33098192 It's possible that my understanding is completely wrong, but your comment is at odds with my other reading, so it would be useful to get some clarification.
- sdenton4 4y agoThis is correct, as I understand it. Most complexity measures are defined in terms of asymptotic behavior, so any specific finite algorithm has 'constant' complexity. This is an obviously unhelpful bit of pedantry in the theory side. In fact, it's as you say; we can compute a 'raw' complexity for a finite operation (eg, raw count of arithmetic ops), and then use that operation as a primitive to create an algorithm with an asymptotic complexity which depends directly on the finite operation's 'raw' complexity. (complexity theory, and specifically for matrix multiplication, is a great example of metrics becoming targets becoming bad incentives, a la Goodhart's Law. The so-called best algorithms are 'galactic' and therefore of no use to anyone. There's some fuzzy-headed hope that one day the people chasing the big-O exponent metric will come up with something practically useful, buuuuuut... you actually gotta work practical problem to solve the practical problem, and that requires different metrics. This seems to be what's motivating the work under discussion here.)
- pxx 4y agosorry; whoops, I don't know why I said multiplications there. I somehow thought the "more additions" somehow meant "fewer multiplications," but no, it's just "more additions but faster performance on target." edited. your other comment notes that for some shapes, even in standard arithmetic, they have found algorithms with fewer multiplications than best-known. but those don't seem to extend to an algorithm with better asymptotic complexity for multiplying general matrices. otherwise I'd assume they'd claim them :)