Matrix Chain Multiplication in Python

Matrix Chain Multiplication is one of the most popular problems in Dynamic Programming and we will use Python language to do this task. Here we multiply a number of matrices continuously (given their compatibility) and we do so in the most efficient manner possible.

Matrix Multiplication

Before multiplying any two matrices we need to check for a certain condition of multiplication.

Suppose the matrices are A (size – m*n) and B (size – p*q). For theses two matrices to be multiplied the condition to be satisfied is n=p.

Brute Force Approach

Suppose we are given a chain of 4 matrices with sizes p = [3,4,5,6]. By using brute force technique the cost of this multiplication would be:

Multiplication Order : (((A*B)*C)*D)  ,  Multiplication Cost: 3*4*5 + 3*4*6 + 3*6*5 = 222

Dynamic Programming Approach

In Dynamic Programming we divide the problem into smaller sub problems, solve them and store their results in a table. We will use these stored values to find the final result.

In this particular problem, we will determine how to arrange the matrices in order to perform the multiplication with least cost.

The basic algorithm is as follows :

 C[i,j] = min { C[i,k] + C[k+1,j] + d[i-1]*d[k]*d[j] } where i<=k<j

Code:

Now see our Python code below:

import sys

p = [3,4,5,6]

def MatrixChainOrder(p):
    n = len(p)
    #create the table to store solutions to sub problems
    m = [[0 for x in range(n)] for x in range(n)]
 
    # l is the length of the chain
    for l in range(2,n):

        for i in range(1,n-l+1):
            j = i+l-1

            #store a maximum integer in the table for further comparison

            m[i][j] = sys.maxsize

            for k in range(i,j):

                #q holds the value of multiplication cost till j elements

                q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]

                #compare previous cost with q

                if q < m[i][j]:

                    m[i][j]=q

    #last element of first row contains the result to the entire problem

    return m[1][n-1]

Output :

MatrixChainOrder(p)
150

Here we see that by using dynamic programming programming approach, we reduce the cost of multiplication from 222 to 150.

Note : In matrix Chain Multiplication we are not bothered about the actual multiplication of the matrices, we simply want to minimize the cost of multiplication.

Hope this was useful.

For similar problems on Algorithms, refer: Job Sequencing Problem using Greedy method in Python

Leave a Reply

Your email address will not be published. Required fields are marked *