# Matrix chain multiplication: Greedy approach

some suggested a thread in which the algorithm multiplies the 2 matrices with lowest values first. Mine is different: it divides by parenthesis the 2 matrices. And continues to the next section.

The problem is: finding the most efficient way to multiply a series of matrices together, using an algorithm of some sort, and comparing these algorithms to find the most efficient one.

The dynamic algorithm approach works at a time complexity of theta of N^3.

My question is, what is the runtime of this algorithm:

A= 5x2 B= 2x7 C= 7x3

1) First, find the matrix with the lowest dimension ( a matrix which has the lower number from the rows or columns of all the matrices).

*If the lowest number is in the last dimension, it is the same like putting the entire sequence in parentheses.

*There is no guidance as to what to do if the lowest number appears twice in the sequence, so I suggest the algorithm just takes 1 randomly.

2) Then divide the sequence to 2: (A)(B•C). The parentheses will close on the matrix from the right and open on the next matrix. This way they will divide the series to 2 parts.

Then repeat the process for the 2 parts. Stop when you have 1 (or 2) matrices in the sequence.

Is this algorithm optimal? It has to be better than N^3 (the usual algorithm)

• cs.stackexchange.com/questions/48280/… – eru-cs Dec 15 '19 at 11:38
• Does this answer your question? Matrix Chain Multiplication Greedy Approach – Yuval Filmus Dec 15 '19 at 11:53
• No. It actually gives a good example to my algorithm.. – John Appleboim Dec 15 '19 at 12:28
• Does "find the lowest number in the lines / rows column" mean finding lowest number from the numbers of rows or columns? You find 2 in your example, right? What if lowest number appears twice, e.g. A=3x2 B=2x2 C=2x5? – Ryoji Dec 15 '19 at 14:47
• I hope I understand your approach. What about 1x2, 2x4, 4x2? – Hendrik Jan Dec 15 '19 at 16:28

Consider the product $$ABC$$, where

• $$A$$ is $$5\times 2$$
• $$B$$ is $$2\times 3$$
• $$C$$ is $$3\times 100$$

Your algorithm first computes $$BC$$ (600 products) and then $$A(BC)$$ (1000 products), for a total of 1600 products.

The optimal solution first computes $$AB$$ (30 products) and then $$(AB)C$$ (1500 products), for a total of only 1530 products.

Suppose that $$A$$ is $$a\times b$$, that $$B$$ is $$b \times c$$, and that $$C$$ is $$c\times d$$. There are two possibilities:

• Compute $$AB$$ and then $$(AB)C$$: cost is $$abc + acd = ac(b+d)$$.
• Compute $$BC$$ and then $$A(BC)$$: cost is $$bcd + abd = bd(a+c)$$.

The first option is preferable if $$\frac{b+d}{bd} < \frac{a+c}{ac}$$ or equivalently $$\frac{1}{b} + \frac{1}{d} < \frac{1}{a} + \frac{1}{c}.$$ For example, above we have $$a = 5$$, $$b = 2$$, $$c = 3$$, $$d = 100$$. Since $$\frac{1}{2} + \frac{1}{100} < \frac{1}{5} + \frac{1}{3},$$ the order $$(AB)C$$ is preferable.

Your decision procedure would prefer this order if $$c < b$$, that is, if $$\frac{1}{b} < \frac{1}{c}.$$ Your condition misses the contribution of $$a,d$$.

• Thank you! Is there a more general rule that applies to longer chains of matrices? Very insightful! – John Appleboim Dec 17 '19 at 14:03
• You can do the calculation yourself and see whether a simple condition arises. – Yuval Filmus Dec 17 '19 at 15:06
• Nice formulas! And I was right about 1x2, 2x4, 4x2. – Hendrik Jan Dec 18 '19 at 14:15