Chain Matrix Multiplication ·Recurrence -Let C(i,j)be the optimal cost of multiplying Ai,...A -C(i,i)=0 for any i(No multiplication needed) -C(i,j)minisksj-1 {C(i,k)+C(k+1,j)+mi-1mkmj} fori≤j-1 Build an N-by-N matrix to store the C(i,j)'s Our optimal value is then C(1,N) mi m1(A)
Chain Matrix Multiplication • Recurrence – Let C(i,j) be the optimal cost of multiplying Ai , … Aj – C(i,i) = 0 for any i (No multiplication needed) – C(i,j) = mini ≤ k ≤ j-1 { C(i,k) + C(k+1,j) + mi-1mkmj } for i ≤ j-1 • Build an N-by-N matrix to store the C(i,j)’s • Our optimal value is then C(1,N) (Ai ) mi mi-1
Example Let A1 be a 5-by-20 matrix,A,be a 20-by-10 matrix,Aa be a 10-by-3 matrix,Aa be a 3-by-2 matrix -m0=5,m1=20,m2=10,m3=3,m4=2 i八j 1 2 3 4 1 0 2 0 3 0 4 0
Example • Let A1 be a 5-by-20 matrix, A2 be a 20-by-10 matrix, A3 be a 10-by-3 matrix, A4 be a 3-by-2 matrix – m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 i \ j 1 2 3 4 1 0 2 - 0 3 - - 0 4 - - - 0
Example 。m0=5,m1=20,m2=10,m3=3,m4=2 ● C(1,2)=C(1,1)+C(2,2)+mom1m2=5·20·10 =1000 C(2,3)=,C(3,4)=· i八j 1 2 3 4 1 0 1000 2 0 3 0 4 0
Example • m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 • C(1,2) = C(1,1) + C(2,2) + m0m1m2 = 5 · 20 · 10 = 1000 • C(2,3) = , C(3,4) = . i \ j 1 2 3 4 1 0 1000 2 - 0 3 - - 0 4 - - - 0
Example 。m0=5,m1=20,m2=10,m3=3,m4=2 0 C(1,2)=C(1,1)+C(2,2)+mom1m2=5·20·10 =1000 C(2,3)=600,C(3,4)=60. i八j 1 2 3 4 1 0 1000 2 0 600 3 0 60 4 0
Example • m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 • C(1,2) = C(1,1) + C(2,2) + m0m1m2 = 5 · 20 · 10 = 1000 • C(2,3) = 600, C(3,4) = 60. i \ j 1 2 3 4 1 0 1000 2 - 0 600 3 - - 0 60 4 - - - 0