Python - Matrix Chain Multiplication

Python – Matrix Chain Multiplication

The Matrix Chain Multiplication problem is a classic dynamic programming challenge. It involves finding the most efficient way to multiply a chain of matrices. Since matrix multiplication is associative, the order in which you perform the multiplications can drastically affect the overall number of scalar multiplications required.

Problem Statement

Given a chain of matrices A₁, A₂, ..., A_n with dimensions defined by an array p of size n+1 (where matrix A_i has dimensions p[i-1] x p[i]), determine the minimum number of scalar multiplications required to compute the product A₁ x A₂ x ... x A_n. Note that you are not required to perform the actual multiplications but only to decide the order that minimizes the cost.

Sample Input and Output

Example 1:

</>

Copy

# Input:
p = [10, 30, 5, 60]

# Explanation:
# There are 3 matrices:
# A1: 10 x 30
# A2: 30 x 5
# A3: 5 x 60
#
# Optimal order: (A1 x A2) x A3
# Cost = (10*30*5) + (10*5*60) = 1500 + 3000 = 4500

# Output:
4500

Explanation: Multiplying A1 and A2 first minimizes the multiplication cost. After computing A1 x A2, the resulting matrix is then multiplied by A3, leading to a total cost of 4500 scalar multiplications.

Example 2:

</>

Copy

# Input:
p = [40, 20, 30, 10, 30]

# Explanation:
# There are 4 matrices:
# A1: 40 x 20
# A2: 20 x 30
# A3: 30 x 10
# A4: 10 x 30
#
# The optimal multiplication order yields a minimum cost of 26000 scalar multiplications.

# Output:
26000

Explanation: By testing different parenthesizations, the dynamic programming solution determines that the optimal way to multiply these matrices requires only 26000 scalar multiplications, significantly reducing the cost compared to a non-optimal order.

Solution Approach

The solution uses dynamic programming by breaking the problem into smaller subproblems. The key idea is to determine the optimal way to split the chain of matrices. The recurrence relation used is:

m[i][j] = min ( m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j] ) for all i ≤ k < j

Here, m[i][j] represents the minimum number of scalar multiplications needed to compute the matrix product from A_i to A_j. The term p[i-1] * p[k] * p[j] calculates the cost of multiplying the resulting matrices after the split. The base case is when i == j, meaning there is a single matrix, so no multiplication is needed (m[i][i] = 0).

Python Program

Method: Iterative Dynamic Programming

</>

Copy

def matrix_chain_order(p):
    """
    Compute the minimum number of scalar multiplications needed
    to multiply the chain of matrices with dimensions given in p.
    
    Parameters:
    p (list): A list of dimensions such that the i-th matrix has dimensions p[i-1] x p[i].
    
    Returns:
    int: Minimum number of scalar multiplications required.
    """
    n = len(p) - 1  # Number of matrices
    # Create a 2D DP table m where m[i][j] stores the minimum cost of multiplying A[i] through A[j]
    m = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    
    # m[i][i] is 0 for all i since the cost of multiplying one matrix is zero.
    
    # L is the chain length.
    for L in range(2, n + 1):
        for i in range(1, n - L + 2):  # 1-indexed; adjust indices accordingly
            j = i + L - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                # Cost = cost of multiplying A[i..k] + cost of multiplying A[k+1..j] + cost of multiplying the two resulting matrices
                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]

# Test examples
print("Matrix Chain Multiplication - Iterative DP")
# Example 1
p1 = [10, 30, 5, 60]
print("Minimum multiplications for p1:", matrix_chain_order(p1))  # Expected output: 4500

# Example 2
p2 = [40, 20, 30, 10, 30]
print("Minimum multiplications for p2:", matrix_chain_order(p2))  # Expected output: 26000

Explanation: In this program, a 2D table m is used where m[i][j] stores the minimum cost to multiply matrices from A_i to A_j. We incrementally increase the chain length (L) and calculate the cost for every subchain by trying all possible splits. The optimal cost for the entire chain is then found at m[1][n].

Conclusion

The Matrix Chain Multiplication problem demonstrates the power of dynamic programming by breaking down a complex problem into manageable subproblems. The iterative dynamic programming approach shown here efficiently computes the minimum number of scalar multiplications needed to multiply a chain of matrices, making it a valuable technique for optimizing computational tasks in various applications.

TutorialKart

Python – Matrix Chain Multiplication