1. Show the correctness of Strassen's algorithm. That is, show that the seven multiplications of that...

 

Transcribed Image Text:

1. Show the correctness of Strassen's algorithm. That is, show that the seven multiplications of that algorithm combine to ensure that the computed product is A1 A2 B | B2 = A3 A4 B3 BA AB1+A2B3 | A1B2 + A2B4 A3B1A4B3 A3B2+ A4B4 2. Show the steps that Strassen's algorithm takes to compute the product 5 4 7 3 1 0 2 1 0 1 0 1 4 1 1 0 0 1 3 0 0 4 11 45 19 = 8 13 7 5 0 2 1 5 8 7 7 2 1 20 1 3 5 0 Exit the recursion when n = 2-i.e., compute the products of the 2 x 2 matrices using the brute force algorithm. 1. Show the correctness of Strassen's algorithm. That is, show that the seven multiplications of that algorithm combine to ensure that the computed product is A1 A2 B | B2 = A3 A4 B3 BA AB1+A2B3 | A1B2 + A2B4 A3B1A4B3 A3B2+ A4B4 2. Show the steps that Strassen's algorithm takes to compute the product 5 4 7 3 1 0 2 1 0 1 0 1 4 1 1 0 0 1 3 0 0 4 11 45 19 = 8 13 7 5 0 2 1 5 8 7 7 2 1 20 1 3 5 0 Exit the recursion when n = 2-i.e., compute the products of the 2 x 2 matrices using the brute force algorithm.