Fast algorithm for matrix chain multiplication in special case

Question

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.

Answer 1

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.