Smart Matrix Multiplication

Let the matrices be $M_1, M_2, \ldots, M_n$ in order. Suppose $a_0, a_1, a_2, \ldots, a_n$ be positive integers such that the dimension of matrix $M_i$ is $a_{i-1} \times a_i$ .

Note that the last product formed must be of the form $M_1 M_2 \ldots M_i$ multiplied by $M_{i+1} M_{i+2} \ldots M_n$ for some $i \in [1, n-1]$ . The first term is an $a_0 \times a_i$ matrix, and the second term is an $a_i \times a_n$ matrix, so the cost of this multiplication is $a_0 a_i a_n$ . Additionally, we need to add the cost of finding each term. The good thing is that the cost of finding each term is independent from each other, so we want to minimize the cost of each term (so that the sum is also as small as possible). This means each term itself is the same problem but with a smaller size. This means we can use dynamic programming to solve it.

The idea is as follows. Suppose we have the optimal cost to compute the product $M_i M_{i+1} \ldots M_j$ for all $i,j$ except $(i,j) = (p,q)$ . Let $f(i,j)$ be this cost. If we want to compute $M_p M_{p+1} \ldots M_q$ as the product of $M_p M_{p+1} \ldots M_i$ times $M_{i+1} M_{i+2} \ldots M_q$ , the total cost is $f(p,i) + f(i+1,q) + a_{p-1} a_i a_q$ . We want to minimize this, so we can simply iterate over all valid $i$ :

$f(p,q) = \min_{i \in [p,q-1]} f(p,i) + f(i+1,q) + a_{p-1} a_i a_q$

And how do we find the values of $f(p,i)$ and $f(i+1,q)$ ? Easy, just use the same thing! Note that $i-p, q-(i+1) < q-p$ ; the difference of the two arguments is smaller. The base case is $f(p,p) = 0$ for all $p$ , because the product of one matrix is just the same matrix, no multiplication required. Thus we can now construct the algorithm: we compute $f(p,q)$ one by one, starting from one with smallest $q-p$ (namely 0, the base case above) until we reach $q-p = n-1$ , where we will find the value of $f(1,n)$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

a = [30, 13, 16, 32, 2, 6, 19, 11, 19, 16, 27, 7, 18, 1, 32, 21, 12, 3, 8, 2, 29,
     28, 2, 24, 4, 13, 13, 1, 3, 22, 25, 14]
n = len(a) - 1
f = dict()

for p in range(1, n+1): f[p, p] = 0
for diff in range(1, n):
    for start in range(1, n-diff+1):
        f[start, start+diff] = min(f[start, i] + f[i+1, start+diff] + a[start-1]*a[i]*a[start+diff]
                                   for i in range(start, start+diff))

print(f[1, n])
# 6450