Python Program to Solve Matrix-Chain Multiplication using Dynamic Programming with Bottom-Up Approach

This is a Python program to solve matrix-chain multiplication using dynamic programming with bottom-up approach.

In the matrix-chain multiplication problem, we are given a sequence of matrices A(1), A(2), …, A(n). The aim is to compute the product A(1)…A(n) with the minimum number of scalar multiplications. Thus, we have to find an optimal parenthesization of the matrix product A(1)…A(n) such that the cost of computing the product is minimized.

1. Two functions are defined, matrix_product and print_parenthesization.
2. The function matrix_product takes a list p as argument.
3. p[0… n] is a list such that matrix A(i) has dimensions p[i – 1] x p[i].
4. It creates two 2D tables m and s as a list of lists.
5. The function stores the minimum number of scalar multiplications needed to compute the product A(i) x A(i + 1) x … x A(j) in m[i][j].
6. The index of the matrix after which the above product is split in an optimal parenthesization is stored in s[i][j].
7. The function finds the minimum computations needed to evaluate A(start) x … x A(end) and stores it in m[start][end].
8. This is done by finding a k such that m[start][k] + m[k + 1][end] + p[start – 1]*p[k]*p[end] is minimized. The last term is the cost of multiplying the two products formed by splitting the matrix-chain after matrix k.
9. The function first sets m[i][i] = 0 for 1 <= i <= n where n is the number of matrices.
10. The function then computes m[i][i + chain_length – 1] for each value of i using the above formula.
11. The above step is performed for each chain_length in [2, n] starting with chain_length = 2.
12. It then returns m and s.
13. The function print_parenthesization takes as argument a 2D table s as generated above.
14. It also takes two indexes start and end as arguments.
15. It prints the optimal parenthesization of the matrix-chain product A(start) x … x A(end).

Here is the source code of a Python program to solve the matrix-chain multiplication problem using dynamic programming with bottom-up approach. The program output is shown below.

def matrix_product(p):
    """Return m and s.
 
    m[i][j] is the minimum number of scalar multiplications needed to compute the
    product of matrices A(i), A(i + 1), ..., A(j).
 
    s[i][j] is the index of the matrix after which the product is split in an
    optimal parenthesization of the matrix product.
 
    p[0... n] is a list such that matrix A(i) has dimensions p[i - 1] x p[i].
    """
    length = len(p) # len(p) = number of matrices + 1
 
    # m[i][j] is the minimum number of multiplications needed to compute the
    # product of matrices A(i), A(i+1), ..., A(j)
    # s[i][j] is the matrix after which the product is split in the minimum
    # number of multiplications needed
    m = [[-1]*length for _ in range(length)]
    s = [[-1]*length for _ in range(length)]
 
    for i in range(1, length):
        m[i][i] = 0
 
    for chain_length in range(2, length):
        for start in range(1, length - chain_length + 1):
            end = start + chain_length - 1
            q = float('inf')
            for k in range(start, end):
                temp = m[start][k] + m[k + 1][end] + p[start - 1]*p[k]*p[end]
                if temp < q:
                    q = temp
                    s[start][end] = k
            m[start][end] = q
 
    return m, s
 
 
def print_parenthesization(s, start, end):
    """Print the optimal parenthesization of the matrix product A(start) x
    A(start + 1) x ... x A(end).
 
    s[i][j] is the index of the matrix after which the product is split in an
    optimal parenthesization of the matrix product.
    """
    if start == end:
        print('A[{}]'.format(start), end='')
        return
 
    k = s[start][end]
 
    print('(', end='')
    print_parenthesization(s, start, k)
    print_parenthesization(s, k + 1, end)
    print(')', end='')
 
 
n = int(input('Enter number of matrices: '))
p = []
for i in range(n):
    temp = int(input('Enter number of rows in matrix {}: '.format(i + 1)))
    p.append(temp)
temp = int(input('Enter number of columns in matrix {}: '.format(n)))
p.append(temp)
 
m, s = matrix_product(p)
print('The number of scalar multiplications needed:', m[1][n])
print('Optimal parenthesization: ', end='')
print_parenthesization(s, 1, n)

1. The user is prompted to enter the number of matrices, n.
2. The user is then asked to enter the dimensions of the matrices.
3. matrix_product is called to get the tables m and s.
4. m[1][n] is the minimum cost of computing the matrix product.
5. print_parenthesization is then called to display the optimal way to parenthesize the matrix product.

Case 1:
Enter number of matrices: 3
Enter number of rows in matrix 1: 10
Enter number of rows in matrix 2: 100
Enter number of rows in matrix 3: 5
Enter number of columns in matrix 3: 50
The number of scalar multiplications needed: 7500
Optimal parenthesization: ((A[1]A[2])A[3])
 
Case 2:
Enter number of matrices: 6
Enter number of rows in matrix 1: 10
Enter number of rows in matrix 2: 100
Enter number of rows in matrix 3: 50
Enter number of rows in matrix 4: 200
Enter number of rows in matrix 5: 25
Enter number of rows in matrix 6: 25
Enter number of columns in matrix 6: 50
The number of scalar multiplications needed: 218750
Optimal parenthesization: (((((A[1]A[2])A[3])A[4])A[5])A[6])
 
Case 3:
Enter number of matrices: 1
Enter number of rows in matrix 1: 4
Enter number of columns in matrix 1: 2
The number of scalar multiplications needed: 0
Optimal parenthesization: A[1]

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.