Assuming n is a power of 2, find the exact number of scalar additions and multip
ID: 3862386 • Letter: A
Question
Assuming n is a power of 2, find the exact number of scalar additions and multiplications needed by Strassen’s algorithm to multiply two n × n matrices. Your answer will depend on the threshold used to stop making recursive calls. Bearing in mind what you learnt in Section 7.2, propose a threshold that minimizes the total number of scalar operations.
You can take for granted that 15 additions and 7 multiplications of n / 2 × n / 2 matrices to multiply two n × n matrices by the Strassen method, n as much as n is even
Explanation / Answer
At most 8 multiplications and 4 additions are necessary to multiply two 2×2 matrices. Thus, the multiplication of two n×n matrices needs at most n3 multiplication and n3-n2 additions. This algorithm reduces the number of multiplications at the expense of higher number of additions.