Tutorial on Dynamic Programming - Concluding Part

This is the concluding part of the series of tutorials on Dynamic Programming. In this part we will see and assimilate one example where the problem of Matrix Chain Multiplication will be solved with Dynamic Programming Principle

What is this Matrix Chain Multiplication Problem?

Suppose we have a sequence or chain A₁, A₂, …, A_n of n matrices to be multiplied. That is, we want to compute the product A₁A₂…A_n. Now there are many possible ways (parenthesizations) to compute the product.

Let us consider the chain A₁, A₂, A₃, A₄ of 4 matrices. Now to compute the product A₁A₂A₃A_4, there are 5 possible ways as described below:

(A₁(A₂(A₃A₄))), (A₁((A₂A₃)A₄)), ((A₁A₂)(A₃A₄)), ((A₁(A₂A₃))A₄), (((A₁A₂)A₃)A₄)

Each of these options may lead to the different number of scalar multiplications, and we have to select the best one (option resulting fewer number of Scalar Multiplications)

Hence the problem statement looks something like:  “Parenthesize the product A₁A₂…A_n such that the total number of scalar multiplications is minimized”

Please remember that the objective of Matrix Chain Multiplication is not to do the multiplication physically, rather the objective is to fix the way of that multiplication ordering so that the number of scalar multiplication gets minimized.

Give me one real example

Ok. But before I show you one real example, let us revisit the algorithm which multiplies two matrices. It goes like following:

Input: Matrices A_p×q and B_q×r (with dimensions p×q and q×r)

Result: Matrix C_p×r resulting from the product A·B

MATRIX-MULTIPLY(A_p×q , B_q×r)

1.            for i ← 1 to p

2.                                            for j ← 1 to r

3.                                                            C[i, j] ← 0

4.                                                            for k ← 1 to q

5.                                                                            C[i, j] ← C[i, j] + A[i, k] · B[k, j]

6.            return C

In the above algorithm, scalar multiplication in line 5 dominates time to compute C Number of scalar multiplications = pqr

Now on the basis of above algorithm what if we try to multiply three matrices A_10´100, B_100´5, and C_5´50?

There are 2 ways to parenthesize

–        ((AB)C) = D_10´5 · C_5´50

•          AB Þ 10·100·5=5,000 scalar multiplications

•          DC Þ 10·5·50 =2,500 scalar multiplications

•          Total number of scalar multiplications 7,500

–        (A(BC)) = A_10´100 · E_100´50

•          BC Þ 100·5·50=25,000 scalar multiplications

•          AE Þ 10·100·50 =50,000 scalar multiplications

•          Total number of scalar multiplications 75,000

It is evident that the first option will result the fewer number of scalar multiplication and it is the best one for computational easiness.

Hope now you understand what I mean.

How do you know that this problem could be solved through Dynamic Programming?

See, there are some clear evidences that this problem is perfect fit to be solved through Dynamic Programming.

In connection to the Matrix Chain Multiplication, the optimal solution to the problem contains within it the optimal solution to subproblems. That is why we can say that this problem will better be solved by Dynamic Programming. Now the question is how we came to a conclusion that the principle of optimality holds true in this case?

Looking back to the problem, we are given with a chain A₁, A₂, …, A_n of n matrices, where for i=1, 2, …, n, matrix A_i has dimension p_i-1´p_i. We need to search for optimal solution of  parenthesization in order  to minimize the scalar computation.

Hence to find the structure of the optimal solution –

§       

       Let us use the notation A_i..j for the matrix that results from the product A_i A_i+1 … A_j

§    

        Let us admit that an optimal parenthesization of the product A₁A₂…A_n splits the product between A_k and A_k+1 for some integer k where1 ≤ k < n

§     

            So we have to compute matrices A_1..k and A_k+1..n  first; then multiply them to get the final matrix A_1..n

The Key observation here is the parenthesizations of the subchains A₁A₂…A_k and A_k+1A_k+2…A_n must also be optimal if the parenthesization of the chain A₁A₂…A_n is optimal.

Hence Dynamic Programming Principle could effectively be used for Matrix Chain Multiplication problem.

What is the Dynamic Programming approach particularly for this problem?

Let m[i, j] be the minimum number of scalar multiplications necessary to compute A_i..j . So minimum cost to compute A_1..n is m[1, n]

Suppose the optimal parenthesization of A_i..j splits the product between A_k and A_k+1 for some integer k where i ≤ k < j. Hence A_i..j = (A_i A_i+1…A_k)·(A_k+1A_k+2…A_j)= A_i..k · A_k+1..j

We get Cost of computing A_i..j = cost of computing A_i..k + cost of computing A_k+1..j + cost of multiplying A_i..k and A_k+1..j

Now Cost of multiplying A_i..k and A_k+1..j is p_i-1p_k p_j

So evidently m[i, j ] = m[i, k] + m[k+1, j ] + p_i-1p_k p_j   for i ≤ k < j and m[i, i ] = 0 for i=1,2,…,n

But optimal parenthesization occurs at one value of k among all possible i ≤ k < j, so check all these and select the best one.

So the optimal substructure relation is like following:

m[i, j ] =  0                                                                              if i=j

               min {m[i, k] + m[k+1, j ] + p_i-1p_k p_j }                      if i<j

             i ≤ k< j

To keep track of how to construct an optimal solution, we use a table s. s[i, j ] = value of k at which A_i A_i+1 … A_j is split for optimal parenthesization.

Wait a minute, I got almost everything except that p array what is it? Where did it come from?

The P array stores the dimensions of the matrices. Suppose we are to multiply 3 matrices of dimension 5* 10, 10* 3 and 3*8, in this case the length of p array will be (3+1) 4 and it will be like P[0] =  5, p[1] = 10, p[2] = 3 and p[3]=8.

So generalizing, if you have n matrices to be multiplied, take the length of p as n+1, then fill p[0] with row number of 1^st matrix, fill p[n] with column no of nth matrix, and for the intermediate indices go like following

P[1] = col no of 1^st matrix or row no of 2^nd matrix

P[2] = col no of 2^nd matrix or row no of 3^rd matrix

P[3] = col no of 3^rd matrix or row no of 4^th matrix

…….

P[n-1] = col no of (n-1)th matrix or row no of nth matrix.

Now I got it. Anyways, how is the algorithm?

Input: Array p[0…n] containing matrix dimensions and n

Result: Minimum-cost table m and split table s

MATRIX-CHAIN-ORDER(p[ ], n)

                for i ← 1 to n

                                m[i, i] ← 0

                for l ← 2 to n

                                for i ← 1 to n-l+1

                                                j  ← i+l-1

                                                m[i, j] ← ¥

                                                for k ← i to j-1

                                                                q ← m[i, k] + m[k+1, j] + p[i-1] p[k] p[j]

                                                                if  q < m[i, j]

                                                                                m[i, j] ← q

                                                                                s[i, j] ← k

return m and s

Can you please give me a C code for Matrix Chain Multiplication 

Here is the code. This code fills up the split table but never utilizes it to show the proper ordering of parenthesis. That part is left for you guys to explore.

This program takes the length of the chain of matrices, and the p array where the dimension of arrays are stored and computes the minimum number of scalar multiplications. 

There is no comment. Try to comment it by your own..this will give you the insights of the program

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<limits.h>

int compute(int*dimArray, int**splitTab, int start, int end)

{

    int iter, sTableEntry;

    int minimumCountOfScalarMultiplications = INT_MAX;

    int countOfScalarMultiplications;

    if(start == end)

             return 0;

    else

    {

        for(iter = start; iter < end; iter++)

        {

                    countOfScalarMultiplications = compute(dimArray, splitTab, start,iter)+ compute(dimArray, splitTab, iter+1, end)+(dimArray[start - 1]*dimArray[iter]*dimArray[end]);

                    if(countOfScalarMultiplications < minimumCountOfScalarMultiplications)

                    {

                                                    minimumCountOfScalarMultiplications = countOfScalarMultiplications;

                                                    sTableEntry = iter;

                    }

        } 

        splitTab[start][end] = sTableEntry;     

    }

    return minimumCountOfScalarMultiplications;

}

int main(void)

{

    int* processedInput;

    int lengthOfChain;

    int iter;

    int** splitTable;   

    printf("\n Enter the length of the chain::");

    scanf("%d", &lengthOfChain);

    processedInput = (int*)malloc(lengthOfChain+1*sizeof(int));

    splitTable = (int**)calloc(lengthOfChain + 1, sizeof(int*));

    for(iter = 0; iter<lengthOfChain; iter++)

             splitTable[iter] = (int*)calloc(lengthOfChain + 1 , sizeof(int));

    printf("\n Enter the dimension of the matrix = ");

    for(iter = 0; iter<=lengthOfChain; iter++)

        scanf("%d", &processedInput[iter]);

    printf("\n Your Input Is Registered Successfully.... Press any key to continue");

    getch();

    printf("\n The number of minimum scalar multiplication = %d", compute(processedInput,splitTable,1, lengthOfChain));

    getch();

    return 0;

}                 

Sample Input

Enter the length of the chain::6

Enter the dimension of the matrix =30 35 15 5 10 20 25

Sample Output

The number of minimum scalar multiplication = 15125