3
$\begingroup$

An exercise from the book Foundations of Algorithms Using Java Pseudocode:

Write an efficient algorithm that will find an optimal order for multiplying $n$ matrices $A_1 \times A_2 \times \ldots \times A_n$, where the dimension of each matrix is $1 \times 1$, $1 \times d$, $d \times 1$ or $d \times d$ for some constant $d$.

The standard dynamic programming approach is $\mathcal{O}(n^3)$, thus probably not much efficient. Hu-Shing algorithm (a link to their paper) works in $\mathcal{O}(n \log n)$ but it's rather an overkill for much simplified version of the problem. I have a concept for quite simple, greedy based, algorithm working in $\mathcal{O}(n \log n)$ but the main difficulty I have is in proving its corectness. First, let's observe what is the cost of multiplication of two matrices of given dimensions and what are the dimensions of their product (column - first matrix, row - second matrix):

  Cost:                           Product:
  dxd |  -   -  d^2 d^3           dxd |  -   -  dx1 dxd
  1xd |  -   -   d  d^2           1xd |  -   -  1x1 1xd
  dx1 |  d  d^2  -   -            dx1 | dx1 dxd  -   -
  1x1 |  1   d   -   -            1x1 | 1x1 1xd  -   -
      +----------------               +----------------
        1x1 1xd dx1 dxd                 1x1 1xd dx1 dxd

If we look at the tables above more closely, we can notice a nice property, that a cheap multiplication gives as a result a matrix that is also likely to be multiplied cheaply. A bit more formally, if we imagine a graph with four nodes representing dimensions of matrix and declare that there is a weighted arc from node M to N if and only if matrix M multiplied by some matrix gives matrix N, with weight of this arc equal to the cost of that multiplication (so every node has exactly two outgoing arcs and exactly two ingoing arcs), then we'll see that graph has two connected components, one of which has arcs that tend to have smaller weights than these in the other one.

This would suggest sticking to that cheap CC at any cost (hehe) and order types of multiplications that we prefer in this way (for brevity, now [ab] denotes a matrix of dimensions $a \times b$):

[11]x[11] < [1d]x[d1] < [11]x[1d] < [d1]x[11] < 
[1d]x[dd] < [dd]x[d1] < [d1]x[1d] < [dd]x[dd] (*)

So a greedy approach would be to have a priority queue which maintains the order of matrices in the following way:

matrix [ab] comes before matrix [cd] if and only if
[ab]x[a'b'] < [cd]x[c'd'] with respect to order (*), 
where [a'b'] is a matrix immediately to the right of matrix [ab], 
and [c'd'] similarly.

and always take its minimum, memorize somewhere that we multiply that matrix with its neighbour on the right, and then replace these two matrices with their product.

Does anyone see a counterexample to this approach or have an idea for a proof of correctness?

UPDATE

I was too convinced that it works just after testing few trivial inputs that passed, that I focused only on devising a proof. However, thanks to D.W. I sobered up and tested it on bigger input - and soon enough I found a counterexample: for this sequence of matrices

[1d] [d1] [11] [11] [1d] [dd] [dd] [d1] [1d] [d1] [11] [1d]

The dynamic algorithm gives the following tree of parenthesization (it's quite easy to see we can model it via a tree)

[1d] [d1] [11] [11] [1d] [dd] [dd] [d1] [1d] [d1] [11] [1d]
   [11]     |    |     \    \    [d1]      [11]    /    /
     |      |    |      \    [d1]              [11]    /
     |      |    |       [11]                  /      /  
     |      |    |          \                 /      /
     |      |    |           ------[11]-------      /
     |      |    |                  /              / 
     |      |    [11]---------------              /
     |       \   /                               /
     |       [11]                               /
      \        /                               /
       --[11]--                               /
           \                                 /
            --------------[1d]---------------

With a total cost: $5+4d+2d^2$.

Whereas the greedy one gives:

[1d] [d1] [11] [11] [1d] [dd] [dd] [d1] [1d] [d1] [11] [1d]
   [11]      [11]    /    /    /    /      [11]    /    /
     \        /     /    /    /    /         \    /    /
      \-[11]-/     /    /    /    /           [11]    /
          \       /    /    /    /              \    /
           --[1d]-    /    /    /                [1d]
                \    /    /    /                  /
                 [1d]    /    /                  /
                    \   /    /                  /
                     [1d]   /                  /
                       \   /                  / 
                        [11]                 /
                           \                /
                            ------[1d]------

With total cost: $3+6d+2d^2$.

And we can see that for any $d > 1, \quad 3+6d+2d^2 > 5+4d+2d^2$, so it's not optimal...

So the competition changes: is it at all possible to solve that problem greedily? Or more broadly (and essentially getting back to the original question from the book) - how could we solve it efficiently (I believe it should be $\mathcal{o}(n^2)$) without resorting to Hu-Shing algorithm? I don't have any ideas unfortunately.

$\endgroup$
  • $\begingroup$ @D.W. - thank you for comment. For some reason I forgot about obvious places to start ;). I also updated my post. $\endgroup$ – socumbersome Jun 7 '14 at 13:14
  • $\begingroup$ I suspect the following is true: unless all of the input matrices are $d\times d$, you never need to multiply a $d\times d$ by a $d\times d$ (there exists an optimal solution that never does that). This means there exists an optimal solution whose total cost is $a d^2 + b d + c$ for some $a,b,c$ (satisfying $a+b+c=n-1$). Does this help? I don't know. $\endgroup$ – D.W. Jun 7 '14 at 20:37
  • $\begingroup$ I suspect the following is also true: unless all of the input matrices are $d\times d$, you never need to have any intermediate result that is a $d \times $ matrix (there always exists an optimal solution where none of the intermediate results are $d \times d$). Not sure whether that helps enough, either. $\endgroup$ – D.W. Jun 7 '14 at 20:40
1
$\begingroup$

Perhaps this solution is incorrect. Feel free to provide counterexamples. I'll provide you with both my solution and the reasoning.

The cost function turns out to be a cubic function in $d$, and the attempt is to minimise the coefficients of the highest power terms. Only possible problem with this approach is that if

$$pd^{3}+qd^{2}+rd+s$$

and

$$wd^{3}+xd^{2}+rd+s$$

are two solutions with $p < w$ then the first solution is only good as long as $(q-x)d < (p-w)$

It however seems like such a situation is impossible to generate (correct me if I am wrong.)

My solution:

  1. Go to the first $[dd]$ matrix. Since it is the first occurrence of $[dd]$, it should either be the first matrix or there should be a $[1d]$ matrix to the left of it. Multiply these matrices. Do this for every $[dd]$ matrix.
  2. To take care of $[dd]$ matrices that are the first in the list, start from the right this time. There should be a $[d1]$ matrix to the right of $[dd]$ matrix unless its the last. Multiply them.
  3. This should get rid of all $[dd]$ matrices unless the input only has $[dd]$ matrices, as pointed out by @D.W. This approach is correct because each $[dd]$ matrix can contribute either a $d^2$ or a $d^3$. This ensures that their contribution is the least.
  4. Every $[1d]$ matrix should now have $[d1]$ matrix to its right, since $[dd]$ matrices have been removed. (unless the $[1d]$ matrix is the last one.) Multiply them.
  5. This should leave you with no $[1d]$ and $[d1]$ matrices unless they are the last and the first ones respectively. This can only happen if they were the last and the first in the original list of matrices as well. This suggests that there is no way to have these matrices generate a $[11]$.
  6. Preform all $[11]$ multiplications.
  7. Finally you'd be left with anywhere from 1 to 3 matrices. Between these it doesn't matter how you perform multiplications.

At point 5 the multiplication of matrices was stalled to the end. This is because, when stalled till the end they'll contribute a $d^2$ or $d$ depending on whether the end result is $[dd]$ or not. Clearly we can't do better since a result of $[dd]$ requires at least $d^2$ operations on the last multiplication.

$\endgroup$
  • $\begingroup$ Unfortunately I'm not able to follow your reasoning. First (and minor) doubt is - should we include $d^3$ term in the total cost? As @D.W. pointed out, it's highly probable we won't have such terms unless all matrices are $[dd]$. Second and more important - where does the assumption that coefficients of $d$ and $d^0$ are equal in all conceivable solutions come from? I fail to see that. $\endgroup$ – socumbersome Jun 9 '14 at 14:35
  • $\begingroup$ @socumbersome Read points 1-3 (mainly 3) of the post. I did read his comment. Please keep in mind that there are instances of this problem where the only solution has a cost equal to $d^3$ as well. Secondly, I was trying to present a situation where my reasoning/algorithm fails to produce an optimum output. Like I said, I based my algorithm around the fact that I want to maintain minimum coefficients of higher order terms. If a situation arises where coefficients of $d$ and $d^0$ are same, and $p < w$, solution is only good as long as $(q-x)d < (p-1)$. $\endgroup$ – shebang Jun 9 '14 at 16:15
  • $\begingroup$ @socumbersome Read through the algorithm I wrote first and see if it makes sense to you. $\endgroup$ – shebang Jun 9 '14 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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