In plain words: Karatsuba splits big multiplications into smaller ones to cut the count, but its extra additions cost more than they save. Applying the same split to matrices keeps the savings while making those additions cheaper, and chips beat standard matrix multiplication on performance per area.
Abstract · Karatsuba Matrix Multiplication and its Efficient Custom Hardware Implementations
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 complexity of the original Karatsuba algorithm while reducing the complexity of the extra additions. Furthermore, we propose new matrix multiplication hardware architectures for efficiently exploiting this extension of the Karatsuba algorithm in custom hardware. We show that the proposed algorithm and hardware architectures can provide real area or execution time improvements for integer matrix multiplication compared to scalar Karatsuba or conventional matrix multiplication algorithms, while also supporting implementation through proven systolic array and conventional multiplier architectures at the core. We provide a complexity analysis of the algorithm and architectures and evaluate the proposed designs both in isolation and in an end-to-end deep learning accelerator system compared to baseline designs and prior state-of-the-art works implemented on the same type of compute platform, demonstrating their ability to increase the performance-per-area of matrix multiplication hardware.
Trevor E. Pogue, Nicola Nicolici
arXiv:2501.08889 · cs.AR, cs.AI, cs.PF · submitted Jan 15, 2025
abstract · pdf · html · Accepted for publication in IEEE Transactions on Computers; Associated source code available on github at https://github.com/trevorpogue/algebraic-nnhw
Anatoly Karatsuba himself was already dead (he died in 2008). I emailed his daughter Yekaterina (who is also a mathematician, btw) asking for a permission to use their last name. She agreed, but asked to be extra careful about potential implicit affiliations, i.e. to be clear that the content has nothing to do with her father's research.
She also expressed an opinion that in the field of mathematics and computation, at least in Russia, actual researchers are rarely involved in writing textbooks, and the textbooks used in universities often contain conflicting or even wrong information about the authorship of research.
In the end a different name was chosen for the project.