(a) Let M=M, X M X M X M4, where the Mj, j = 1..4, are matrices. The order of each matrix is given as follows: M is 10 X 20; M2 is 20 X 15; M3 is 15 X 50 and M is 50 X 5.
(1) Using the Dynamic Programming method (See Appendix C), calculate m, 4 to complete the table below which determines the least number of multiplications which can be used to compute M. [3 marks] m1 = 0 m22 = 0 m33 = 0 m44 = 0 m2 = 3000 m3 = 15000 m34 = 3750 10500 5250 m13 m24 m4=
(ii) Determine the computational complexity of the algorithm referenced in part a(i) above. Show all steps in your working.
The correct answer and explanation is :
Part (i): Dynamic Programming to Calculate Minimum Scalar Multiplications
We are given a chain of matrix multiplications ( M_1 \times M_2 \times M_3 \times M_4 ), where the matrices have the following dimensions:
- ( M_1 ) is ( 10 \times 20 )
- ( M_2 ) is ( 20 \times 15 )
- ( M_3 ) is ( 15 \times 50 )
- ( M_4 ) is ( 50 \times 5 )
We are tasked with using the dynamic programming approach to find the minimum number of scalar multiplications required to multiply these matrices.
Dynamic Programming Matrix Chain Multiplication
The dynamic programming method works by breaking down the problem into smaller subproblems and then solving each one optimally. Let’s define ( m[i, j] ) as the minimum number of scalar multiplications needed to compute the matrix chain from ( M_i ) to ( M_j ). The recursive relation for ( m[i, j] ) is:
[
m[i, j] = \min_{i \leq k < j} \left( m[i, k] + m[k+1, j] + p_{i-1} \cdot p_k \cdot p_j \right)
]
Where ( p_i ) denotes the dimension of matrix ( M_i ), i.e., ( M_i ) has dimension ( p_{i-1} \times p_i ).
Step-by-Step Calculation of ( m[i, j] )
Step 1: Define the dimensions
We define the dimensions for each matrix as follows:
- ( p_0 = 10 ), ( p_1 = 20 ), ( p_2 = 15 ), ( p_3 = 50 ), ( p_4 = 5 )
The problem now becomes minimizing the number of scalar multiplications to compute the matrix chain.
Step 2: Initialize the ( m ) table
The diagonal elements of the matrix ( m[i, i] ) are zero because no multiplication is needed for a single matrix.
m[1, 1] = 0
m[2, 2] = 0
m[3, 3] = 0
m[4, 4] = 0Step 3: Fill in the table for increasing chain lengths
Let’s compute for chain lengths 2, 3, and 4.
Chain length 2 (i.e., multiplying two matrices)
- ( m[1, 2] = 10 \times 20 \times 15 = 3000 )
- ( m[2, 3] = 20 \times 15 \times 50 = 15000 )
- ( m[3, 4] = 15 \times 50 \times 5 = 3750 )
Chain length 3 (i.e., multiplying three matrices)
- ( m[1, 3] = \min \left( m[1, 1] + m[2, 3] + 10 \times 20 \times 50, m[1, 2] + m[3, 3] + 10 \times 15 \times 50 \right) ) First calculation:
[
m[1, 3] = 0 + 15000 + 10 \times 20 \times 50 = 0 + 15000 + 10000 = 25000
] Second calculation:
[
m[1, 3] = 3000 + 0 + 10 \times 15 \times 50 = 3000 + 0 + 7500 = 10500
] So, ( m[1, 3] = 10500 ). - ( m[2, 4] = \min \left( m[2, 2] + m[3, 4] + 20 \times 15 \times 5, m[2, 3] + m[4, 4] + 20 \times 50 \times 5 \right) ) First calculation:
[
m[2, 4] = 0 + 3750 + 20 \times 15 \times 5 = 0 + 3750 + 1500 = 5250
] Second calculation:
[
m[2, 4] = 15000 + 0 + 20 \times 50 \times 5 = 15000 + 0 + 5000 = 20000
] So, ( m[2, 4] = 5250 ).
Chain length 4 (i.e., multiplying all four matrices)
- ( m[1, 4] = \min \left( m[1, 1] + m[2, 4] + 10 \times 20 \times 5, m[1, 2] + m[3, 4] + 10 \times 15 \times 5, m[1, 3] + m[4, 4] + 10 \times 50 \times 5 \right) ) First calculation:
[
m[1, 4] = 0 + 5250 + 10 \times 20 \times 5 = 0 + 5250 + 1000 = 6250
] Second calculation:
[
m[1, 4] = 3000 + 3750 + 10 \times 15 \times 5 = 3000 + 3750 + 750 = 7500
] Third calculation:
[
m[1, 4] = 10500 + 0 + 10 \times 50 \times 5 = 10500 + 0 + 2500 = 13000
] So, ( m[1, 4] = 6250 ).
Final Table for Minimum Scalar Multiplications
| i, j | m[i,j] |
|---|---|
| m[1,1] | 0 |
| m[1,2] | 3000 |
| m[1,3] | 10500 |
| m[1,4] | 6250 |
| m[2,2] | 0 |
| m[2,3] | 15000 |
| m[2,4] | 5250 |
| m[3,3] | 0 |
| m[3,4] | 3750 |
| m[4,4] | 0 |
So the minimum number of scalar multiplications to multiply the entire chain of matrices is 6250.
Part (ii): Computational Complexity of the Algorithm
The time complexity of the matrix chain multiplication dynamic programming algorithm is ( O(n^3) ), where ( n ) is the number of matrices in the chain.
Explanation:
- Outer Loops (k, i, j): The algorithm iterates over all subproblems (subchains of matrices) that we need to solve. There are three nested loops:
- The outer loop runs for different chain lengths, from 2 to ( n ).
- The second loop goes through all possible starting points of the chain (i.e., it chooses the first matrix in the chain).
- The innermost loop finds the optimal split of the chain at each position.
- Work per Subproblem: Each subproblem involves a constant amount of work — finding the minimum cost split and calculating the scalar multiplications for that split, which is ( O(1) ).
Thus, the overall complexity is ( O(n^3) ), where ( n ) is the number of matrices in the chain. For ( n = 4 ), the complexity is still ( O(4^3) = O(64) ), which is a manageable size for small chains like the one in this problem.