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 different 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 different orderings = 5 different parenthesizations

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

Each parenthesization is a different 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