Summary
Multiplying two 3 by 3 grids of numbers is important in many computer tasks but can be slow. The authors found a way to do this multiplication with fewer simple steps, like additions and subtractions, by changing the way the numbers are represented. This method uses a special combination of shortcuts and checks to make sure the result is correct. It helps separate the core multiplication work from extra steps needed to switch formats.
What this means in practice
- •For graphics programmers: Optimize small matrix multiplications in rendering pipelines by using a reduced-addition algorithm for faster computations.
- •For signal processing engineers: Integrate a more efficient multiplication method for 3x3 matrices to speed up filter and transform computations in embedded devices.
Authors
Joshua Stapleton, Andrew Perminov
Abstract
We give a rank-23 algorithm for $3\times3$ matrix multiplication using 51 additions and subtractions in alternative bases. The input and output conversions require five further additions, giving 56 additions in ordinary coordinates. The construction combines linear-program reduction with a search over sparse basis changes, and the resulting programs are distributed as a machine-checkable certificate. We verify correctness by exact coefficient expansion and distinguish the kernel cost from the cost of a complete multiplication.