0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ You can already do it in time $O(N)$. $\endgroup$ Commented Mar 24, 2021 at 13:29
  • 1
    $\begingroup$ 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). $\endgroup$
    – user114966
    Commented Mar 24, 2021 at 13:29

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.