Strassen’s algorithm for matrix multiplication relies on using 7 multiplications (instead of 8 as in the...

Strassen’s algorithm for matrix multiplication relies on using 7 multiplications (instead of 8 as in the straightforward algorithm) to multiply a pair of 2 by 2 matrices. Explain why it is not possible to further reduce this number, 7, to anything less than 4, in multiplying a pair of 2 by 2 matrices.

Solutions

Expert Solution

Hey so you want to know why we cannot reduce those 7 multiplications even more, well I can answer that for you and make you understand why we cannot further reduce that 7 number for a 2 by 2 matrix.

There are reason why those multiplications should be at least 7, the reason are:-

The submatrices in recursion take extra space.

You see whenever we are multiplying a 2 by 2 matrix(for this example) we would just simply not be able to have 4 multiplications as you said because 4 multiplications are done on the first iteration itself.

And I'm sure as you know Strassen's algo doesn't do only one iteration, it does multiple iterations to multiply 2 by 2 matrices, and in doing those iterations the total number of multiplications also go up.

In the end we can certainly reduce the number of multiplications but only up to a certain number and that number is 7, not 4 because number of iterations are always going to be greater than 1. Hope you understand it now.

venereology answered 11 months ago

Next > < Previous

Related Solutions

Strassen’s algorithm for matrix multiplication relies on using 7 multiplications (instead of 8 as in the...

Strassen’s algorithm for matrix multiplication relies on using 7 multiplications (instead of 8 as in the straightforward algorithm) to multiply a pair of 2 by 2 matrices. Explain why it is not possible to further reduce this number, 7, to anything less than 4, in multiplying a pair of 2 by 2 matrices.

Need to write a code using c# Strassen’s Algorithm for matrix multiplication.

Recall the Matrix Chain Multiplication Algorithm for determining the optimal parenthesization for a product of matrices....

Recall the Matrix Chain Multiplication Algorithm for determining the optimal parenthesization for a product of matrices. Provide a recursive implementation of the function void print_parenth(Matrix K[], int i, int j); that takes as input the matrix K of k values that are needed to construct the optimal parenthesization for Ai · · · Aj . Assume access to a print function that takes as input a string and prints its value. You may also assume a “+” operation for string...

Write a verilog code for 8-bit signed multiplication using Booth algorithm and represent the RTL view...

Write a verilog code for 8-bit signed multiplication using Booth algorithm and represent the RTL view for code

Consider a variant of the matrix-chain multiplication problem in which the goal is to parenthesize the sequence of matrices so as to maximize, rather than minimize, the number of scalar multiplications.

Consider a variant of the matrix-chain multiplication problem in which the goal is to parenthesize the sequence of matrices so as to maximize, rather than minimize, the number of scalar multiplications. Does this problem exhibit optimal substructure?

Recall the Matrix-Multiplication Algorithm for determining all-pairs distances in a graph. Provide a linear-time recursive implementation...

Recall the Matrix-Multiplication Algorithm for determining all-pairs distances in a graph. Provide a linear-time recursive implementation of the function void print_path(Matrix D[], int n, int i, int j); that takes as input the array of matrices D[1], D[2], . . . , D[n − 1] that have been computed by the algorithm, and prints the optimal path from vertex i to vertex j. Hint: for convenience you may use the notation Dr ij to denote the value D[r][i, j], i.e....

Demonstrate Karatsuba’s algorithm for multiplying integers using just three half-size multiplications as detailed below. Assume that...

Demonstrate Karatsuba’s algorithm for multiplying integers using just three half-size multiplications as detailed below. Assume that you can use a calculator to do all operations (half-size (2 or 3 digit) multiplication, and adding, subtracting, and shifting of any size), but write down everything you do. (you are also encouraged to use a calculator to check your process by doing the 4-digit multiplication directly). Suppose we want to multiply 3275 · 2876. Write here the three half-size products that you are...

Prove that GL(2, Z2) is a group with matrix multiplication

2. Using matrices, create an algorithm that takes a matrix of dimension N x N and...

2. Using matrices, create an algorithm that takes a matrix of dimension N x N and feed it in a spiral shape with the sequential number from 1 to N^2. Then do an algorithm in PSEint

Trace through of Dijkstra’s Algorithm, using vertex v5 as the source vertex. Here is adjacency matrix...

Trace through of Dijkstra’s Algorithm, using vertex v5 as the source vertex. Here is adjacency matrix representing the graph with n = 6 vertices: 1 2 3 4 5 6 1 0 999 5 8 999 4 2 9 0 999 999 12 3 3 999 10 0 2 9 999 4 999 999 999 0 999 999 5 999 7 17 999 0 11 6 5 999 11 16 2 0 Initially we have: vnear = 5. Fill array...

Subjects