Matrix Chain Multiplication#

Welcome to Day 34 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Matrix Chain Multiplication, a classic optimization problem that demonstrates the power of dynamic programming.

What is Matrix Chain Multiplication?#

Matrix Chain Multiplication is an optimization problem that seeks to find the most efficient way to multiply a chain of matrices. The problem is not to actually perform the multiplications, but rather to decide the order in which the matrices should be multiplied.

Problem Statement#

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.

Why is this Important?#

The order in which we multiply matrices can significantly affect the total number of operations needed. For example, if we have three matrices A, B, and C with dimensions 10x30, 30x5, and 5x60 respectively:

• (AB)C = (10x30x5) + (10x5x60) = 1500 + 3000 = 4500 operations
• A(BC) = (30x5x60) + (10x30x60) = 9000 + 18000 = 27000 operations

Choosing the right order (AB)C saves us 22,500 operations!

Naive Recursive Approach#

Let’s start with a naive recursive implementation:

 1def matrix_chain_order_naive(p, i, j):
 2    if i == j:
 3        return 0
 4
 5    min_cost = float('inf')
 6
 7    for k in range(i, j):
 8        cost = (matrix_chain_order_naive(p, i, k) +
 9                matrix_chain_order_naive(p, k + 1, j) +
10                p[i-1] * p[k] * p[j])
11
12        if cost < min_cost:
13            min_cost = cost
14
15    return min_cost
16
17# Example usage
18p = [10, 30, 5, 60]
19n = len(p)
20print(f"Minimum number of multiplications is {matrix_chain_order_naive(p, 1, n-1)}")

This approach has a time complexity of O(2^n), making it inefficient for larger inputs.

Dynamic Programming Approach#

We can significantly improve the efficiency using Dynamic Programming.

Top-Down Approach (Memoization)#

 1def matrix_chain_order_memo(p):
 2    n = len(p)
 3    m = [[0 for _ in range(n)] for _ in range(n)]
 4    
 5    def matrix_chain_helper(i, j):
 6        if i == j:
 7            return 0
 8        if m[i][j] != 0:
 9            return m[i][j]
10        
11        m[i][j] = float('inf')
12        for k in range(i, j):
13            q = (matrix_chain_helper(i, k) +
14                 matrix_chain_helper(k + 1, j) +
15                 p[i-1] * p[k] * p[j])
16            if q < m[i][j]:
17                m[i][j] = q
18        return m[i][j]
19    
20    return matrix_chain_helper(1, n-1)
21
22# Example usage
23p = [10, 30, 5, 60]
24print(f"Minimum number of multiplications is {matrix_chain_order_memo(p)}")

Bottom-Up Approach (Tabulation)#

 1def matrix_chain_order_tab(p):
 2    n = len(p)
 3    m = [[0 for _ in range(n)] for _ in range(n)]
 4    
 5    for L in range(2, n):
 6        for i in range(1, n - L + 1):
 7            j = i + L - 1
 8            m[i][j] = float('inf')
 9            for k in range(i, j):
10                q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
11                if q < m[i][j]:
12                    m[i][j] = q
13    
14    return m[1][n-1]
15
16# Example usage
17p = [10, 30, 5, 60]
18print(f"Minimum number of multiplications is {matrix_chain_order_tab(p)}")

Both Dynamic Programming approaches have a time complexity of O(n^3) and a space complexity of O(n^2).

Printing the Optimal Parenthesization#

We can modify our solution to also print the optimal way to parenthesize the product:

 1def matrix_chain_order_with_parenthesization(p):
 2    n = len(p)
 3    m = [[0 for _ in range(n)] for _ in range(n)]
 4    s = [[0 for _ in range(n)] for _ in range(n)]
 5    
 6    for L in range(2, n):
 7        for i in range(1, n - L + 1):
 8            j = i + L - 1
 9            m[i][j] = float('inf')
10            for k in range(i, j):
11                q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
12                if q < m[i][j]:
13                    m[i][j] = q
14                    s[i][j] = k
15    
16    def print_optimal_parens(s, i, j):
17        if i == j:
18            print(f"A{i}", end="")
19        else:
20            print("(", end="")
21            print_optimal_parens(s, i, s[i][j])
22            print_optimal_parens(s, s[i][j] + 1, j)
23            print(")", end="")
24    
25    print("Optimal Parenthesization: ", end="")
26    print_optimal_parens(s, 1, n-1)
27    print()
28    return m[1][n-1]
29
30# Example usage
31p = [10, 30, 5, 60]
32print(f"Minimum number of multiplications is {matrix_chain_order_with_parenthesization(p)}")

Applications of Matrix Chain Multiplication#

1. Optimization in linear algebra computations
2. Parsing in Natural Language Processing
3. Optimizing database query plans
4. RNA secondary structure prediction in bioinformatics

Exercise#

1. Implement a function that returns the actual sequence of matrix multiplications, not just the parenthesization.

2. Modify the algorithm to handle the case where some matrices cannot be multiplied together (i.e., their dimensions are incompatible).

3. Implement a variation of the problem where each matrix multiplication has an associated cost (not just based on dimensions), and find the optimal order to minimize total cost.

Summary#

Today, we explored Matrix Chain Multiplication, a classic optimization problem that demonstrates the power of dynamic programming. We implemented various approaches, from naive recursion to optimized dynamic programming solutions, and even a version that provides the optimal parenthesization.

Understanding Matrix Chain Multiplication and its solutions provides valuable insights into dynamic programming techniques and their applications in optimization problems, particularly those involving sequences of operations.

Tomorrow, we’ll dive into another fundamental dynamic programming problem: the Longest Increasing Subsequence. Stay tuned!

Solution#

 1def matrix_multiplication_order(p):
 2    n = len(p)
 3    m = [[0] * n for _ in range(n)]
 4    s = [[0] * n for _ in range(n)]
 5    for L in range(2, n):
 6        for i in range(1, n - L + 1):
 7            j = i + L - 1
 8            m[i][j] = float('inf')
 9            for k in range(i, j):
10                q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
11                if q < m[i][j]:
12                    m[i][j], s[i][j] = q, k
13
14    steps = []
15    def collect(i, j):
16        if i == j:
17            return f"A{i}"
18        k = s[i][j]
19        left = collect(i, k)
20        right = collect(k + 1, j)
21        result = f"M{len(steps) + 1}"
22        steps.append(f"{result} = {left} x {right}")
23        return result
24
25    collect(1, n - 1)
26    return steps
27
28# Example usage
29for step in matrix_multiplication_order([10, 30, 5, 60]):
30    print(step)