0
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to the site! Thanks for noticing the big gap in the existing answers and doing something to fill it. $\endgroup$ – David Richerby Nov 19 '18 at 16:38
  • 1
    $\begingroup$ To second @DavidRicherby, this should be the accepted answer. $\endgroup$ – Apass.Jack Nov 19 '18 at 16:40
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The fact that memoization doesn't make everything faster says nothing whatsoever about whether it would make this algorithm faster. For example, one could equally well answer the question "Would divide and conquer make matrix multiplication any faster?" with "No. Divide and conquer isn't some magical keyword you can apply to anything to make it faster." Except that Strassen does make matrix multiplication faster using divide and conquer. $\endgroup$ – David Richerby Nov 19 '18 at 16:32
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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