Floating point operations in a zero padded Strassen multiplication

Question

So I've seen other posts here that do discuss this, but I'm not quite sure how the time complexity (I think?) relates to the actual number of floating point operations done per second when you're changing the size of the matrix you're working on. The time taken is of course the same each time, since it is padded to a size $N(>n)$ which is a power of 2. So the number of floating point operations is also according to the new dimension $N$, right?

So for example, what's mentioned in this answer and the other answers there wouldn't exactly be the same for the actual number of floating point operations, right? Since all the zeros added at the beginning would be used in the computations anyway?

As I'm doing this right now, my, say 450 sized matrix multiplication takes about the same time as the 512 one, but that's expected. When calculating the floating point operations, they would be according to the larger N, right?

Answer 1

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.

Now if you want to calculate floating-point operations per second, then you might consider instead to calculate useful floating-point operations per second and not count operations x times 0 and z = z + x times 0 coming from padding.

Answer 2

See, the idea is to choose the next power of $2$ for $n$ so that we have $\frac{N}{2} < n \le N$. Then, in an asymptotic sense, it does not matter whether you use $n$ or $N$. Here's why:

The actual complexity for multiplying padded matrixes of size $N \times N$ is $O(N^{\log_2 7})$. Now $N^{\log_2 7} < (2n)^{\log_2 7} = 2^{\log_2 7} \times n^{\log_2 7} = 7\times n^{\log_2 7} = O(n^{\log_2 7})$.