# matrix multiplication speedup when the matrix elements are 0, 1 and -1

I would like to compute matrix multiplication A * B where A is Nx3 and B is 3x3. We also know that the elements of B only contains 0, 1, and -1. The content of A is arbitrary floats.

Is there any speedup we can do?

• You can already do it in time $O(N)$. Commented Mar 24, 2021 at 13:29
• Did you verify that you need this speedup (using profiler)? If you did, what kind of speedup do you need (2x, 10x)? Since there are $3^{9} \approx 20,000$ values of $B$, for each possible $B$ you can create a function $f_B$ s.t. $f_B(A) = A \cdot B$. Some optimizations are possible there, since you can ignore $0$ elements. Won't make the computation much faster on average (can even make it slower because of code cache issues).
– user114966
Commented Mar 24, 2021 at 13:29

## 1 Answer

Per row of A you would perform 9 multiplication and six additions, which you could perform with 3 multiplications and 6 fused multiply-add instructions. Like

ResultX = ax * c00 + bx * c01 + cx * c02
ResultY = ax * c10 + bx * c11 + cx * c12
ResultZ = ax * c20 + bx * c21 + cx * c22


Use a switch for the 27 possible values of c00, c10 and c20. Then we need just the fma’s and even replace one of them with a plain multiplication in case one of these numbers is zero.