.

# Chain Matrix Multiplication Algorithm Assignment Help

- Let U be an n by m matrix, let V be an m by p matrix, then W = UV is an n by p matrix.
- W = UV could be computed within O(nmp) time, using traditional matrix multiplication.
- Suppose I want to compute U1U2U3U4.
- Matrix Multiplication is associative, so perform the multiplication in a number of diﬀerent orders.

## Chain Matrix Multiplication Algorithm Example:

- U1 is 10 by 100 matrix
- U2 is 100 by 5 matrix
- U3 is 5 by 50 matrix
- U4 is 50 by 1 matrix
- U1U2U3U4 is a 10 by 1 matrix

### 5 diﬀerent orderings = 5 diﬀerent parenthesizations

- ( U1( U2( U3U4 )))
- (( U1U2 )( U3U4 ))
- ((( U1U2 ) U3 ) U4)
- (( U1 ( U2U3 )) U4)
- ( U1 (( U2U3 ) U4 ))

Each parenthesization is a diﬀerent number of mults

Let Uij = Ui • • •Uj

U1 is 10 by 100 matrix, U2 is 100 by 5 matrix, U3 is 5 by 50 matrix, U4 is 50 by 1 matrix, U1U2U3U4 is a 10 by 1 matrix.

- ( U1 ( U2 ( U3U4 )))
- U34 = U3U4 , 250 mults, outcome is 5 by 1
- U24 = U2U34 , 500 mults, outcome is 100 by 1
- U14 = U1U24 , 1000 mults, outcome is 10 by 1
- Total is 1750

- (( U1U2 )( U3U4 ))
- U12 = U1U2, 5000 mults, outcome is 10 by 5
- U34 = U3U4, 250 mults, outcome is 5 by 1
- U14 = U12U34, 50 mults, outcome is 10 by 1
- Total is 5300

- ((( U1U2 ) U3) U4)
- U12 = U1U2, 5000 mults, outcome is 10 by 5
- U13 = U12U3, 2500 mults, outcome is 10 by 50
- U14 = U13U4, 500 mults, outcome is 10 by 1
- Total is 8000

- U1 is 10 by 100 matrix, U2 is 100 by 5 matrix, U3 is 5 by 50 matrix, U4 is 50 by 1 matrix, U1U2U3U4 is a 10 by 1 matrix.
- (( U1( U2U3 )) U4)
- U23 = U2U3, 25000 mults, outcome is 100 by 50
- U13 = U1U23, 50000 mults, outcome is 10 by 50
- U14 = U13U4, 500 mults, outcome is 10 by
- Total is 75500

- ( U1 (( U2U3 ) U4))
- UA23 = U2U3, 25000 mults, outcome is 100 by 50
- U24 = U23U4, 5000 mults, outcome is 100 by 1
- U14 = U1U24, 1000 mults, outcome is10 by 1
- Total is 31000

.