Matrix Chain Multiplication

Matrix chain multiplication is an optimization Problem that can be solved using dynamic programming. Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved.We have many options to multiply a chain of matrices because matrix multiplication is associative. 

Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]. We need to write a function that should return the minimum number of multiplications needed to multiply the chain. For example

Input: p[] = {10, 20, 30, 40, 30}

Output: 30000

Explanation: There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30. Let the input 4 matrices be A, B, C and D. The minimum number of multiplications are obtained by putting parenthesis in following way ((AB)C)D --> 10*20*30 + 10*30*40 + 10*40*30

 

 Code For Matrix Chain Multiplication in Python 

def MatrixChainOrder(p, n):

    # For simplicity of the program, one extra row and one

    # extra column are allocated in m[][].  0th row and 0th

    # column of m[][] are not used

    m = [[0 for x in range(n)] for x in range(n)]

    # m[i,j] = Minimum number of scalar multiplications needed

    # to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where

    # dimension of A[i] is p[i-1] x p[i]    # cost is zero when multiplying one matrix.

    for i in range(1, n):

        m[i][i] = 0

 

    # L is chain length.

    for L in range(2, n):

        for i in range(1, n-L+1):

            j = i+L-1

            m[i][j] = sys.maxint

            for k in range(i, j):

                # q = cost/scalar multiplications

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

                if q < m[i][j]:

                    m[i][j] = q

    return m[1][n-1]

Analysis:

Time Complexity: O(n^3)
Auxiliary Space: O(n^2)

Contributor's Info

Created:
0Comment