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).
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]))
In [7]:
print(compute([('A', 10, 20), ('B', 20, 30), ('C', 30, 40)]))
In [8]:
print(compute([('A', 13, 5), ('B', 5, 89), ('C', 89, 3), ('D', 3, 34)]))
In [9]:
print(compute([('A', 12, 2), ('B', 2, 82), ('C', 82, 3100), ('D', 3100, 250), ('E', 250, 3), ('F', 3, 90)]))