Skip to main content
1 of 2
gnasher729
  • 31.6k
  • 35
  • 55

You wouldn’t pad to a power of two.

First, for small matrix sizes you would just produce the fastest code you can, without using Strassen at all. Then you figure out for which n a 2n x 2n matrix is multiplied using one step of the Strassen method, and if the size is odd, you increase by 1. So the total increase will be much less than a power of two.

So for your 450x450 example, you multiply 225x225, then 113x113, 57x57, 29x29, and if you find that Strassen for 15x15 is no improvement then you have calculated a 464x464 product. Much faster than 512x512.

gnasher729
  • 31.6k
  • 35
  • 55