How many floating-point operations for Strassen's algorithm for a matrix of size k x k?

Question

I am trying to understand this analysis of Strassen's algorithm for multiply k x k matrices. But I am still not too sure how many operations are invovled. Can someone help clarify this?

Answer 1

The number of operations performed is determined as follows. First, we split the matrix up into four sub strives of size at k/2, and then perform seven recursive multiplications of those matrices. We then do a constant number of additions of those products to get our desired result. This gives us a recurrence relation defined as follows:

T(1) = 1

T(k) = 7T(k/2) + ck²

Note that lg 7 > 2, since lg 7 > lg 4 = 2. (Here, lg is the binary logarithm). Thus by case one of the Master theorem, the asymptotic complexity of the algorithm is O(k^{lg 7}) ≈ O(k^2.807).

Hope this helps!

Answer 2

Given the page says it is approximately O(N^2.807...) I would guess that would be a good approximation of the number of floating-point operations. All the looping/iterating will be with integer operations.