Matrix Chain Multiplication

We got a assignment problem from our IC 303 DATA STRUCTURES AND ALGORITHMS , I’ll be going into its portions in detail too. But for today’s post I will solve the following problem of Matrix Chain Multiplication and hope the explanation of this problem will help bring clarity to how useful dynamic problem can be in solving problems.

The Assignment Problem

Find the cost involved in finding the product of 6 Matrices using both

1. Dynamic programming (Matrix Chain Multiplication)
2. Normal matrix multiplication.

Given,

$$S = A_{30\times35} . B_{35\times15} . C_{15\times5} . D_{5\times10} . E_{10\times20} . F_{20\times25}$$

Now first of all, what is cost here? I think its reasonable to assume the cost (time complexity) can be thought of as the total number of scalar multiplications to obtain $S$.

For calculating $P$ given that,

$$C = A_{p \times q} \times B_{q \times r}$$

its trivial to prove that the number of scalar multiplications required are $p \times q \times r$.

For each element of $P$ we need to do $q$ multiplications, for the first row of $C$ we have $r$ such elements(size of each row), so $q \times r$ multiplications.

Finally we have $p$ such rows (number of rows), so total number of scalar multiplications to calculate $C$ is $p \times q \times r$

For example check out the image below where $p, q, r$ are 4,2,3.

Normal matrix multiplication.

Ok, now we have defined what is cost let’s see what the cost of the Normal Multiplication of the The Assignment problem is,

now by normal multiplication lets consider the grouping as shown below,

$$S = ( ( ( ( (A_{30\times35} . B_{35\times15}) . C_{15\times5}) . D_{5\times10}) . E_{10\times20}) . F_{20\times25})$$

So here first $A \times B$ is done in $15750, (30 \times 35 \times 15)$
then that solution with $C$ is done in $2250, (30 \times 15 \times 5)$
then that solution with $D$ is done in $1500, (30 \times 5 \times 10)$
then that solution with $E$ is done in $6000, (30 \times 10 \times 20)$
then that solution with $F$ is done in $15000, (30 \times 20 \times 25)$

Thus in the Normal method we need to perform $40500$ scalar multiplications.

Now it should be obvious we can find $S$ by different methods which will change as we change how we group the 6 matrices.

Therefore the matrix-chain multiplication problem is given a chain of $n$ matrices to multiply, we need to find the grouping which minimizes the total number of scalar multiplications

In most cases the time we spend to find this special grouping is more than made up by the savings in the effort to actually compute the solution.

Now ok cool, we now know that we need to group these $n$ matrices, what’s the total number of ways that can be done?

Going by brute force then using the native algorithm the time complexity is,

$$\Omega({4^n}/{n^{ \frac{3}{2}} })$$

while we get $O(n^3)$ for the dynamic programming solution to finding the grouping.

So we can agree we need to use dynamic programming to optimally parenthesize a matrix chain.

Dynamic programming

I hope you all know that Divide and conquer algorithms works on the principle that we take a problem, make it into subproblems (divide) and recursively solve it (conquer).

Now what if when you applied this kind of problem solving strategy to a problem and discovered that you were repeating your work. That the subproblems that you were solving weren’t unique… would you solve them again and again? Nope, we would use the solution we already got with the first occurrence of that particular subproblem right?!

So that’s the basic idea of how Dynamic programming works. So when we see a problem with both Overlapping subproblems (this means that the subproblems repeat themselves) and Optimal substructure (which just means that it’s possible to solve this problem optimally by joining the optimally solved subproblems) we can use D.P.

So in the case of this Matrix Chain Multiplication problem what’s this “optimal subproblem” look like?

The crucial idea is that given a set of $n$ matrices then the Matrix Chain Multiplication problem can be broken down to,
Finding $k$ ( $1<k<n$ ) such that both the group of matrices $1$ to $k$ as well as the group of matrices $k+1$ to $n$ are optimally arranged for multiplication.

Thus $Cost([1,n]) = Cost([1,k])+Cost([k+1,n]) + (pqr)$

where p is the number of rows of the first matrix,
q is the number of rows of $k$th matrix
or the number of column of $(k+1)$th matrix,
r is the number of columns of the $n$th matrix.

So here the first two terms are the cost of optimally solving the subproblems (i.e. consider the set of matrices $[1,k]$ and $[k+1,n]$ as subproblems) now when you join those two subproblem solutions you get the optimal solution to the original problem involving $[1,n]$. That’s the key idea here.

$$\Large X = Y Z$$

Optimal solution of $[1,n]$ = $X_{p \times r}$
Optimal solution of $[1,k]$ = $Y_{p \times q}$
Optimal solution of $[k+1,n]$ = $Z_{q \times r}$
The $pqr$ term is incurred by the joining of the two subproblem solutions. (the first solution is a $p \times q$ matrix and the second solution is a $q \times r$ matrix.)

[TO BE CONTINUED]

Written with StackEdit.