principleMinorCanonical
Matrix chain multiplication: Greedy approach
Viewed 0 times
multiplicationgreedymatrixapproachchain
Problem
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)
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)
Solution
Consider the product $ABC$, where
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:
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$.
- $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$.
Context
StackExchange Computer Science Q#118540, answer score: 4
Revisions (0)
No revisions yet.