Gateforum

Question

Total Number of multiplication operations to get the product of two matrices of order 4 *4 using Strassen’s matrix multiplication method is

• A. 50
• B. 60
• C. 64
• D. 56

Comments

shreyansh jain

Actually, it will be something 49.18000353.

So, it can't be 49.18000 multiplications. it should be 49 or 50.

I think we should go for the worst case(ceil) that's why 50.

---

@kumar.dilip

I have written the answer please read it once. Also, check the ref :)

---

https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/05DivideAndConquerII.pdf

Answer 1

If you recall strassen's algorithm, here a matrix is divided into half of the order and then multiply. 

for example if a matrix is of order 4 then it will be divided into 7 2*2 matrix and then multiplication performed on these 7 matrix will be suffice, no extra multiplication required.

T(n) = 7T(n/2) + n^2  // Strassen's Algo reccurence relation

Now in 2*2 matrix you need to perform 8 multiplication.

so for 7 2*2 matrix you need to perform 7*8 multiplication.

Therefore ans will be 56.

P.S. : O(n^2.81) is the time complexity of strassen's algo, it does not give no. of multiplications.

Answer 2

Strassen’s Algorithm allows us to multiply two n by n matrices A and B, with a number of multiplications (and additions) which is a small multiple of $n^{log_27}$ , when n is of the form $2^k$.

The number of multiplication required for any matrix of order $2^k$ is $7^k$

Here, order = 4 => k=2.

The number of multiplication required should be $7^2$ i.e. 49 and not anything between 49 and 50. That additional thing that might be coming is because $O(n^{log_27})$ is the time complexity and not the number of multiplications. Hence, none of the options is correct.

Refer this: http://www-math.mit.edu/~djk/18.310/18.310F04/Matrix_%20Multiplication.html

Comments

I don't think so, it's a shortcoming.

please provide references. And what is wrong with my solution ???

---

Reference is attached already, go through it once.

---

answer given is 56...but i think 50 is correct only