Matrix Chain Multiplication

Matrix Chain Multiplication

The Matrix Chain Multiplication problem is an optimization problem that involves determining the most efficient way to multiply a sequence of matrices in order to minimize the number of scalar multiplications. It is a classic problem in dynamic programming.

Problem Definition:

Given a sequence of matrices, the task is to find the optimal parenthesization of the matrix chain multiplication such that the number of scalar multiplications is minimized.

Matrix Chain Multiplication involves multiplying several matrices. Matrix multiplication is associative, meaning the order of multiplication does not change the result, but it does affect the number of operations required.

For example, given three matrices:

• A of dimension p × q
• B of dimension q × r
• C of dimension r × s

The number of scalar multiplications required to compute the product (A * B) * C is:

• Multiplying A and B requires p * q * r scalar multiplications.
• Multiplying (A * B) with C requires p * r * s scalar multiplications.

But if you instead computed (A * (B * C)), the number of scalar multiplications required might be different, i.e., q * r * s for multiplying B and C, followed by p * q * s for multiplying A and (B * C).

Thus, the goal is to find the optimal parenthesization of the matrices such that the number of scalar multiplications is minimized.

Approach:

This problem is solved using Dynamic Programming (DP), where the idea is to break the problem into smaller subproblems and solve each one, storing the results to avoid redundant calculations.

Steps:

1. Matrix Dimensions:

   • Let A1, A2, ..., An be a sequence of matrices.
   • Let A1 have dimensions p0 × p1, A2 have dimensions p1 × p2, ..., An have dimensions pn-1 × pn.

2. Subproblem:

   • Let m[i][j] represent the minimum number of scalar multiplications needed to multiply matrices Ai through Aj.
   • The goal is to compute m[1][n], which gives the minimum number of scalar multiplications for multiplying all matrices from A1 to An.

3. Recurrence Relation: To compute m[i][j], the matrices can be split into two parts at some point k, where i ≤ k < j. The total cost of multiplying matrices Ai..Aj is the cost of multiplying matrices Ai..Ak and A(k+1)..Aj plus the cost of multiplying the two resulting matrices. This is given by:

   $$m[i][j] = \min_{i \leq k < j} \left( m[i][k] + m[k+1][j] + p_{i-1} \cdot p_k \cdot p_j \right)$$

   where p_{i-1} * p_k * p_j is the cost of multiplying the resulting matrices from subproblems.

4. Base Case:

   • For a single matrix, m[i][i] = 0, as no multiplication is required.

5. Order of Calculation:

   • The problem is solved for increasing lengths of chains, from chains of length 2 to n. For each chain length, the cost for all possible subchains is computed.

Dynamic Programming Algorithm for Matrix Chain Multiplication:

The algorithm computes the minimum number of multiplications in a bottom-up manner and stores the intermediate results in a table m.

Time Complexity:

• Time Complexity: O(n³), where n is the number of matrices. This is because we compute the cost for each subproblem for each possible chain length, and each subproblem requires iterating over all possible split points.
• Space Complexity: O(n²) for storing the DP table m.

C++ Implementation of Matrix Chain Multiplication:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Function to perform matrix chain multiplication
// and return the minimum number of scalar multiplications
int matrixChainOrder(const vector<int>& dims) {
    int n = dims.size() - 1; // Number of matrices (n = number of dimensions - 1)

    // m[i][j] stores the minimum number of multiplications needed
    vector<vector<int>> m(n, vector<int>(n, 0));

    // L is the chain length
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i < n - length + 1; i++) {
            int j = i + length - 1;
            m[i][j] = INT_MAX;

            // Try all possible places to split the chain
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
                m[i][j] = min(m[i][j], q);
            }
        }
    }

    // The result is stored in m[0][n-1]
    return m[0][n - 1];
}

int main() {
    // Example: Matrix dimensions for matrices A1 (10x20), A2 (20x30), A3 (30x40), A4 (40x30)
    vector<int> dims = {10, 20, 30, 40, 30};

    cout << "Minimum number of scalar multiplications: "
         << matrixChainOrder(dims) << endl;

    return 0;
}

Explanation of the Code:

1. Matrix Dimensions:

   • The dims vector represents the dimensions of the matrices. For example, if dims = {10, 20, 30, 40, 30}, then the matrix chain consists of:
     • A1 with dimensions 10x20,
     • A2 with dimensions 20x30,
     • A3 with dimensions 30x40,
     • A4 with dimensions 40x30.

2. DP Table Initialization:

   • m[i][j] stores the minimum number of scalar multiplications needed to multiply matrices from Ai to Aj.
   • Initially, m[i][i] = 0, as multiplying a single matrix requires no multiplication.

3. Filling the DP Table:

   • The code fills the DP table for chains of increasing lengths (starting from length 2 to n).
   • For each chain, it calculates the cost of all possible ways to split the chain and chooses the one with the minimum cost.

4. Result:

   • After filling the table, the minimum number of scalar multiplications required to multiply all matrices is stored in m[0][n-1].

Example Run:

For the input matrix dimensions:

dims = {10, 20, 30, 40, 30}

The optimal parenthesization is:

((A1 * A2) * (A3 * A4)), with the minimum number of scalar multiplications being 26000.

This corresponds to the following steps:

• First, calculate A1 * A2 (10x20 and 20x30), which takes 10 * 20 * 30 = 6000 operations.
• Then calculate A3 * A4 (30x40 and 40x30), which takes 30 * 40 * 30 = 36000 operations.
• Finally, multiply the two results, which takes 10 * 30 * 30 = 9000 operations.

Thus, the total number of scalar multiplications is 6000 + 36000 + 9000 = 26000.

Conclusion:

The Matrix Chain Multiplication problem demonstrates how dynamic programming can be applied to optimize problems that involve making a sequence of decisions, where the order of decisions (in this case, the matrix multiplication order) matters. The approach is efficient and reduces the time complexity from exponential to polynomial time, making it feasible for large input sizes.