Skip to content

Matrix Chain Multiplication

Jump to bottom
Rafiul Islam edited this page Nov 11, 2018 · 3 revisions

Matrices: A(2,3) B(3,6) C(6,4) D(4,5)

Array = [2, 3, 6, 4, 5]

init:

row/col 0 1 2 3
0 0
1 0
2 0
3 0

Length 2

A*B = 2 * 3 * 6 = 36

B*C = 3 * 6 * 4 = 72

C*D = 6 * 4 * 5 = 120

row/col 0 1 2 3
0 0 36
1 0 72
2 0 120
3 0

Length 3

A * B * C

  • (AB)C = 36 + 2 * 6 * 4 = 36 + 48 = 84 min
  • A(BC) = 2 * 3 * 4 + 72 = 24 + 72 = 96

B * C * D

  • B(CD) = 3 * 6 * 5 + 120 = 210
  • (BC)D = 72 + 3 * 4 * 5 = 132 min
row/col 0 1 2 3
0 0 36 84
1 0 72 132
2 0 120
3 0

Length 4

A * B * C * D

  • A(BCD) = 2 * 3 * 5 + 132 = 162
  • (ABC)D = 84 + 2 * 4 * 5 = 124 min
  • (AB)(CD) = 36 + 120 + 2 * 6 * 5
row/col 0 1 2 3
0 0 36 84 124
1 0 72 132
2 0 120
3 0

minimum operation 124

©Rafiul

Clone this wiki locally