3
$\begingroup$

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)

Improve this question
$\endgroup$
7
  • $\begingroup$ cs.stackexchange.com/questions/48280/… $\endgroup$
    – integrator
    Commented Dec 15, 2019 at 11:38
  • 2
    $\begingroup$ Does this answer your question? Matrix Chain Multiplication Greedy Approach $\endgroup$
    – Yuval Filmus
    Commented Dec 15, 2019 at 11:53
  • $\begingroup$ No. It actually gives a good example to my algorithm.. $\endgroup$
    – John Appleboim
    Commented Dec 15, 2019 at 12:28
  • $\begingroup$ 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? $\endgroup$
    – Ryoji
    Commented Dec 15, 2019 at 14:47
  • 1
    $\begingroup$ I hope I understand your approach. What about 1x2, 2x4, 4x2? $\endgroup$
    – Hendrik Jan
    Commented Dec 15, 2019 at 16:28

1 Answer 1

Reset to default
4
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.