# Finding optimal multiplication order and optimal binary tree

I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree.

Consider the following five matrices A, B, C, D and E along with their dimensions;
A=(6×5) B=(5×1) C=(1×7) D=(7×4) E=(4×2)

After two hours, I have calculated the final cost matrix as

0   30   72   82   85
0    35   48   53
0    28   43
0    56
0


and the split k values that led to a minimum m[i, j] value

0   1   2   2   2
0   2   2   2
0   3   4
0   4
0


Now I don't know how to calculate optimal order for multiplication from the above table. And also don't know to draw optimal tree for that sequence. Kindly someone help me at this point.

• Can you explain what is the content of the "final cost matrix" ? What are lines and column related to ? – Vince Jan 22 at 15:11
• @Vince I got rows and columns by this formula m[i, i] = 0 m[i, j] = min i≤k<j (m[i, k] + m[k + 1, j] + (pi−1).(pk)(pj) – Tom Jan 22 at 15:16
• What do you mean by "Optimal Multiplication Order"? Is the goal the minimal number of total multiplications where the multiplication of any two matrixes is done by the definition? – Apass.Jack Jan 22 at 17:25
• @Apass.Jack It means the order of multiplication that minimizes the number of operations – Tom Jan 22 at 18:13
• There are multiplications and additions. Do you want to minimize both together or separately or just multiplications? Note multiplications are generally viewed as much more costly than additions. – Apass.Jack Jan 22 at 18:31

This is the classic problem of matrix chain multiplication.

Here is the pseudocode in Java from Wikipedia, which computes, for each $$2 \le k \le n$$, the minimum costs of all subsequences of length k using the costs of smaller subsequences already computed. It runs in $$O(n^3)$$, where $$n$$ is is the number of matrices, assuming the number of rows and columns in all matrices are bounded by a constant.

// Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
// The first index for dims is 0 and the first index for m and s is 1.
MatrixChainOrder(int dims[])
{
// length[dims] = n + 1
n = dims.length - 1;
// m[i,j] = Minimum number of scalar multiplications (i.e., cost)
// needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
// The cost is zero when multiplying one matrix
for (i = 1; i <= n; i++)
m[i, i] = 0;

for (len = 2; len <= n; len++) { // Subsequence lengths
for (i = 1; i <= n - len + 1; i++) {
j = i + len - 1;
m[i, j] = MAXINT;
for (k = i; k <= j - 1; k++) {
cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
if (cost < m[i, j]) {
m[i, j] = cost;
s[i, j] = k; // Index of the subsequence split that achieved minimal cost
}
}
}
}
}


You can check that Wikipedia page for more information. In particular, there is a ready-make java implementation. There is also explanation to a much more complicated algorithm that runs in $$O(n\log n)$$ time.