Strassen's matrix multiplication algorithm follows .................................................. technique.
Question
Strassen's matrix multiplication algorithm follows .................................................. technique.
Solution
Strassen's matrix multiplication algorithm follows the divide and conquer technique.
Here are the steps:
-
Divide: The given matrices A and B of size n x n are divided into eight sub-matrices of size n/2 x n/2.
-
Conquer: Seven multiplications recursively on the sub-matrices are performed, which are smaller instances of the same problem. This is a recursive step.
-
Combine: The results of the seven multiplications are added or subtracted appropriately to form the product matrix.
This algorithm reduces the number of recursive multiplication calls from 8 to 7 compared to the standard divide and conquer algorithm for matrix multiplication.
Similar Questions
Write a python program for multiplication of 2×3 and 3×2 matrix. Input should be taken from user. Put compiled Program and output snapshot here.
Write a java program to perform matrix multiplicationinput:m-no. of rowsn-no.of columsmatrix1=[]matrix2=[]output:matrix3=[]
solve the matrix chain multiplication problem and achieve the optimal parenthesization.
Perform the matrix multiplication: [3 1; 4 2] * [2 0; 1 3].a.[5 3; 10 6]b.[3 1; 4 2]c.[7 3; 10 6]d.[7 1; 10 4]
What is the time complexity of matrix multiplied recursively by Divide and Conquer Method?ans.O(n3)O(n)O(n2)O(n!) Previous Marked for Review Next
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.