Matrix chain multiplication

Creator
Creator
Seonglae ChoSeonglae Cho
Created
Created
2023 Oct 17 6:29
Editor
Edited
Edited
2023 Oct 19 6:16

Given a chain of matrices

where has dimensions for multiplication
 
 
 

Depends on size of matrix

Parenthesize if important
notion image
 
 
 
Suppose that an optimal parenthesiation of splits the product beween and
Let is the minimum number of multiplications needed to compute
  • - diagonal terms are zero
notion image
fill out direction
for calculate minimum, we need for loop so So we don’t use DP solution
notion image
In reality we use
Heuristic
and approximate algorithm
 
 
 
 
 
 
 
 
 

Recommendations