3
$\begingroup$

I'm trying to gain intuition for writing a matrix chain multiplication algorithm by working through a few problems by hand. I see plenty of worked-through solutions on sets of three or four solutions, but not much for sets bigger than that. But the method I've seen so far is extremely tedious for the scenario I'm attempting:

Find the best way to multiply a chain of matrices with dimensions of $A = 10 \times 5$, $B = 5 \times 2$, $C = 2 \times 20$, $D = 20 \times 12$, $E = 12 \times 4$, and $F = 4 \times 60$. Show your work.

In the smaller examples I've done so far, I was able to simply multiply the dimensions of each -- $AB, BC, ..., EF$ -- and add the minimal values to cover all matrices. I suppose I could do the same on a problem like this, but it would be extremely tiring and I'm wondering if there's a better way than brute force to do this. Help!

$\endgroup$

3 Answers 3

1
$\begingroup$

Start with finding the costs of all subsequences of length 2, then use those to find the minimal costs of all subsequences of length 3, etc. This unfortunately is $O(n^3)$, so it's tedious as you saw.

There is an $n \ln n$ algorithm explained here but from my skimming it looks like it relies on a symmetry that only exists when the resulting matrix is square.

$\endgroup$
0
$\begingroup$

If some of these matrices have special features, e.g. they have many zeroes, then that would help. For generic matrices there is not much more that you can do.

$\endgroup$
0
$\begingroup$

If you can use gauss reduction first or find any diagonizable matrices.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .