Note that matrices multiplication is associative X times Y t

Note that matrices multiplication is associative: X times Y times Z = X times (Y times Z) = (X times Y) times Z. Suppose we want to calculate the product of a series of matrices multiplication: .A_1 times A_2 times A_3 times ... times A_l. The dimension of these matrices are already given in an array dim, = (dim_1, dim_2, ..., dim_l+i), such that A_1 has dimensions dim_1 times dim_2, A_2 has dimensions dim_2 times dim_3, etc. Describe a polynomial time algorithm that determines the best way to associate A_1. A_2, ..., A_l such that the computation cost is minimized? (The proof of correctness and time complexity are also required.)

Solution

matrix multiplication algo

. n = length[p] - 1

for i = 1 to n

do m[i, i] =0

for L =2 to n   

do for i = 1 to n - L+1

do j ¬ i + L - 1

m[i, j] ¬ ¥

for k ¬ i to j - 1

do q ¬ m[i, k] + m[k+1, j] + pi-1 pk pj

if q < m[i, j]

then m[i, j] ¬ q

s[i, j] ¬ k

return m and s