2
$\begingroup$

I am thinking about the derivation of the following dynamic equation: $$F(n_1,...,n_{k+1};k)=\min_{1<i<k+1}\{n_{i-1}n_i n_{i+1}+F(n_1,...,n_{i-1},n_{i+1},...,n_{k+1};k-1)\}, k=1,...,h$$

Let me explain you the details. We have a matrix $M_k$ of dimension $n_k\times n_{k+1}, k\in\{1,...,h\}$. I want to compute $M_1... M_h$. $F(n_1,...,n_{k+1};k)$ is the minimum number of multiplications which we need to get $M_1... M_h$. Now I want to check if the above equation is the correct dynamic programming equation.

I am not sure how to derive the above form. I think it has something to do with cutting the matrix multiplication, i.e I cut $M_1... M_h$ to two matrices of order $n_{i-1}\times n_i$ and $n_i\times n_{i+1}$. So now we need to optimize the subtrees (we we illustrate the whole multiplication as a tree) but I do not see the rest.

$\endgroup$

1 Answer 1

1
$\begingroup$

This is the task of putting brackets in matrix multiplication such that it'll minimize operations count. There's some ambiguity in notation and I'll replace $F(n_1, \dots, n_{k+1}; k)$ with $F(n_1, \dots, n_{k+1})$.
Suppose that we have to put first inner-most brackets. At first step you have to choose a pair of matrices to be multiplicated. If you choose matrices $M_i$ and $M_{i+1}$ and multiply them, that will cost you $n_{i}\cdot n_{i+1}\cdot n_{i+2}$ multiplications. After that you obtain the operation minimizing task for set of matrices $M_1, \dots, M_{i-1}, (M_i \cdot M_{i+1}), M_{i+2}, \dots, M_h$ which costs exactly $$F(n_1,...,n_{i-1},n_i, n_{i+2},...,n_{h+1}).$$ $F(n_1,...,n_{h+1})$ is obtained exactly as a minimum among all inner-most variants of brackets: $F(n_1,...,n_{h+1})=\min \limits_{1<i<h+1}\{n_{i}\cdot n_{i+1}\cdot n_{i+2}+F(n_1,...,n_{i-1},n_{i},n_{i+2},...,n_{h+1})\}$.
Also, you could do that another way. You may choose the outer-most bracket first and it will result in such dynamical equation:

$$F(n_1,...,n_{h+1})=\min_{1<i<h+1}\{n_{1}n_{i+1} n_{h+1} + F(n_1, \dots, n_{i+1}) + F(n_{i+1},\dots, n_{h+1})\}.$$ This corresponds to splitting the product in two brackets $(M_1\cdot\dots\cdot M_i)$ and $(M_{i+1},\dots, M_{h+1})$. To multiplicate them we have to spend $n_1 n_{i+1} n_{h+1}$ iterations. But to multiplicate matrices inside these two brackets we have to spend $F(n_1, \dots, n_{i+1})$ and $F(n_{i+1},\dots, n_{h+1})$ operations respectively. And, again, we take minimum among all variants of outer-most brackets.

$\endgroup$
6
  • $\begingroup$ Thanks for your answer. This makes sense. I was asking myself if it can be concluded that the algorithm which finds the multiplication order requiring least scalar multiplications is the follow: I use the idea from putting inner-most brackets. I first look for the optimal multiplication pair inside the chain, so I check $(M_1 M_2), (M_2 M_3),..., (M_{h-1}M_h)$ and use the most efficient one. Then I repeat the process, correct? $\endgroup$
    – Alkibiades
    Oct 17, 2013 at 13:26
  • $\begingroup$ Yes, you've got it right. You repeat the process of "creating optimization subtasks" until you have to compute something like $F(n_j, n_{j+1}, n_{j+2})$ -- you already now how many operations should be spent on multiplication of two matrices. $\endgroup$
    – Evgeny
    Oct 17, 2013 at 13:36
  • $\begingroup$ Ok, there is one last thing. My lecture notes about optimization and control say that as the value $h$ gets bigger the amount of effort which we need to find the optimal order increases faster than any polynomial function of $h$. I do not see this, do you have an idea? $\endgroup$
    – Alkibiades
    Oct 17, 2013 at 13:42
  • $\begingroup$ I think, if we denote amount of effort for computing optimal bracket arrangement for $h$ matrices as $\#F(h)$, we'll have recurrence like $\#F(h) = (h-1)\cdot \#F(h-1)$. It's very close to factorial of $h$ and of course grows faster than any polynomial. $\endgroup$
    – Evgeny
    Oct 17, 2013 at 13:49
  • $\begingroup$ Thanks for your help again. I went through the wikipedia article about Matrix Chain Multiplication and found en.wikipedia.org/wiki/… Is this still referring to the problem above? $\endgroup$
    – Alkibiades
    Oct 17, 2013 at 14:18

You must log in to answer this question.

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