Let A1, …, An be matrices where the dimensions of Ai are di-1 x di, for i = 1, 2

Question

Let A1, …, An be matrices where the dimensions of Ai are di-1 x di, for i = 1, 2, …, n. Given below is a greedy algorithm to determine the best order in which to perform the matrix multiplications1 to compute A1 x A2 x … x An:

GreedyOrder(dim, n):

At each step, choose the largest remaining dimension (among dim[1], …, dim[n-1]),

and multiply two adjacent matrices that share that dimension.

a. Determine whether this algorithm produces the optimal order of multiplications for the following matrices: A1 which is 30 x 1, A2 which is 1 x 40, A3 which is 40 x 10, and A4 which is 10 x 25. Consider the number of multiplications that would need to be done.

b. Give a convincing argument that this strategy will always minimize the number of multiplications, or give an example where it does not do so.

Explanation / Answer

a. Determine whether this algorithm produces the optimal order of multiplications for the following matrices: A1 which is 30 x 1, A2 which is 1 x 40, A3 which is 40 x 10, and A4 which is 10 x 25. Consider the number of multiplications that would need to be done.

Here Dimensions are 40,30,25,10,1

Step 1: 40 will be sellected( A2XA3 )is groupe for multiplication to get dim 1 X dim 10 matrix

Step 2: 30 will be selected (A1X( A2XA3 )) to get dim 30X dim 10 matrix

But insted of 30 if 25 or 10 was selected them number of multiplation would less

So, The given algorithm does not produce the optimal order.

b. Give a convincing argument that this strategy will always minimize the number of multiplications, or give an example where it does not do so.

Solution:

The given exmple in (a) so that the strategy will not always minimize the number fo multiplication

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.