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, 2020 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, 2020 at 20:25
  • $\begingroup$ Can you explain the notation $d_{i-1,j}$? I only know what $d_i$ stands for. $\endgroup$ Dec 6, 2020 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, 2020 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, 2020 at 23:09

1 Answer 1

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, 2020 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.