2
$\begingroup$

We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$.

In the classical matrix chain multiplication problem, we wish to minimize the total number of scalar multiplications. In this problem, we consider the all intermediate matrices arising in the computation (including the final result but excluding the original matrices), and the cost of a specific order is the maximal number of entries of such an intermediate matrix. As usual, we want to minimize the cost.

As an example, if $n = 2$ the answer is simply $d_0d_2$, and if $n = 3$, then there are two orders:

  • $(A_1A_2)A_3$, in which the intermediate matrices are $A_1A_2,A_1A_2A_3$. The cost is therefore $\max(d_0d_2,d_0d_3)$.
  • $A_1(A_2A_3)$, in which the intermediate matrices are $A_2A_3,A_1A_2A_3$. The cost is therefore $\max(d_1d_3,d_0d_3)$.

Denote by $C_{ij}$ the optimal cost of multiplying $A_i,\ldots,A_j$. We can write the following recurrence for $C_{ij}$:

$$C_{ij}=\min_{i \leq k <j} \max \{C_{i,k},C_{k+1,j},d_{i-1}d_j\},$$

with base case $C_{ii} = 0$.

How do we get this recurrence?

$\endgroup$
8
  • $\begingroup$ I don't understand the definition of $C_{ij}$. $\endgroup$ Dec 6 '20 at 19:53
  • $\begingroup$ I still don't understand what $C_{ij}$ is. Also, I don't understand what $d_{i-1,j}$ is. $\endgroup$ Dec 6 '20 at 20:25
  • $\begingroup$ Can you explain the notation $d_{i-1,j}$? I only know what $d_i$ stands for. $\endgroup$ Dec 6 '20 at 21:05
  • $\begingroup$ If you are not sure about what you are trying to prove, the chance that you will manage to prove it is rather small. $\endgroup$ Dec 6 '20 at 21:16
  • 1
    $\begingroup$ Please edit the question to incorporate all relevant information. Don't just leave clarifications in the comments: use the comments to help you revise the question so it will be clear to future readers. Thank you! $\endgroup$
    – D.W.
    Dec 6 '20 at 23:09
2
$\begingroup$

We get the recurrence by considering all possible ways of breaking up $A_i \times \cdots \times A_j$.

Specifically, we consider $(A_i \times \cdots \times A_k) \times (A_{k+1} \times \cdots \times A_j)$ for all relevant values of $k$, which are $i,\ldots,j-1$.

$\endgroup$
1
  • $\begingroup$ I think it's best if you worked this out on your own. $\endgroup$ Dec 6 '20 at 22:00

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.