[Submitted on 15 Jan 2025]
Abstract:While the Karatsuba algorithm reduces the complexity of large integer multiplication, the extra additions required minimize its benefits for smaller integers of more commonly-used bitwidths. In this work, we propose the extension of the scalar Karatsuba multiplication algorithm to matrix multiplication, showing how this maintains the reduction in multiplication complexi
4 Comments
evolextra
[dead]
oofbey
They're proposing "new hardware architectures" to take advantage of this idea. Anybody with a background in GPU floating point math comment on how realistic this is?
ash-ali
the govy uses specialized hardware that isn't sold on the market right? would something like this be useful in developing said hardware>?
dvasdekis
Would this work have the potential to speed up encoding/decoding of the PAR2 format[0]? This format is widely used to protect datasets against bitrot and small losses, but is held back because of the significant compute overhead when dealing with large datasets.
[0] https://en.wikipedia.org/wiki/Parchive