Would memoization make any improvement to Strassen's algorithm?

Question

Could the run-time of the Strassen's algorithm be improved by adding Memoization to it?

Answer 1

I don't get why the other answerers don't even make an attempt to reason along the lines the question has been asked. If anything, they should explain why memoization can or cannot work.

In any case, let's think about how we can can approach memoization in the Strassen's algorithm. We know that it involves dividing our matrix into four equal quarters, calculating products of individual submatrices and combining them through addition with the following complexity:

$T(N) = 7T(N/2) + O(N^2)$

The one place where we can apply memoization is in the product of the submatrices stage. Each time we encounter two submatrices that need to be multiplied, we can store the result hoping that we encounter the same submatrices again and don't have to recompute the product. This will take up a lot of memory of the order of $O(N^2)$ for each saved product.

That brings us to the next question - How many products are going to be there? We will be having one $N^2$ matrix in the outermost call, $7(\frac{N}{2})^2$ matrices in the next call, $49(\frac{N}{4})^2$ matrices in the subsequent call and so on until $7^{(log N)}$ individual products. You will notice that we're using more and more memory as the recursion depth increases. (The memory requirement will be greater than $O(N^2)$)

Although the memory size is large, what is really important for us is to locate a given matrix from the set of stored matrices. Naively, this would take $O(number\_of\_products \cdot N^2)$ time for iterating through all of the products computed so far. We can probably make it faster by passing the input matrices through a hash function and mapping the hash value to the matrix. This can be done in $O(N^2)$ for the right choice of hash function, and $O(1)$ for a map based lookup.

How will this affect our complexity? We now do an additional lookup before computing the product, and save the product right after as well. $T(N) = O(N^2) + 7T(N/2) + O(N^2) + O(N^2)$. This is equivalent to our original complexity.

This shows us that asymptotically, we don't do worse in terms of time complexity although the space complexity shoots up.

Will it actually speed things up? It really depends on how often we will have repeating submatrices that we need to recompute. I do not think that in any practical scenario (especially if we are dealing with floating point operands), we will see the same sets of submatrices too many times. But this is an intuition. If I were you, I'd try it out and empirically find out if it helps.

Answer 2

No. Memoization isn't some magical keyword you can apply to anything to make it faster.

Answer 3

Nope, We generally use memoization for Dynamic Programming strategy(where we can speed up our programs by storing the results of expensive recursive calls and returning the cached result when the same inputs occur again). Whereas, Strassen's algorithm is a Divide and Conquer strategy.