Day 02 - Matrix chain multiplication


Definition(s)

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 (matrix multiplication is associative).

Algorithm(s)


In [5]:
import numpy as np  # for infinity

In [6]:
def compute(matrices):
    n = len(matrices)  # number of matrices in the chain

    # dp[i, j] = order of multiplication, nr rows, nr cols, cost of mult of subchain [i..j]
    dp = {(i, i): matrices[i] + (0,) for i in range(n)}  # a subchain of only one matrix has cost 0

    # length of subchain
    for i in range(1, n):
        # starting index of subchain
        for j in range(0, n - i):
            best = np.inf  # inf (can be any value that is large enough)

            # splitting point of subchain [j, j + i]
            for k in range(j, j + i):
                lname, lrows, lcols, lcost = dp[j, k]
                rname, rrows, rcols, rcost = dp[k + 1, j + i]

                assert lcols == rrows
                # multiply subchains at splitting point
                cost = lcost + rcost + lrows * lcols * rcols

                if cost < best:
                    best = cost
                    dp[j, j + i] = "(" + lname + rname + ")", lrows, rcols, cost

    return dict(zip(["order", "rows", "cols", "cost"], dp[0, n - 1]))

Run(s)


In [7]:
print(compute([('A', 10, 20), ('B', 20, 30), ('C', 30, 40)]))


{'order': '((AB)C)', 'rows': 10, 'cols': 40, 'cost': 18000}

In [8]:
print(compute([('A', 13, 5), ('B', 5, 89), ('C', 89, 3), ('D', 3, 34)]))


{'order': '((A(BC))D)', 'rows': 13, 'cols': 34, 'cost': 2856}

In [9]:
print(compute([('A', 12, 2), ('B', 2, 82), ('C', 82, 3100), ('D', 3100, 250), ('E', 250, 3), ('F', 3, 90)]))


{'order': '(A((((BC)D)E)F))', 'rows': 12, 'cols': 90, 'cost': 2062600}