2
$\begingroup$

I'm reading CLRS and there is something I don't understand regarding counting the number of parenthesization, in the Matrix-chain multiplication chapter, the book says:

Denote the number of alternative parenthesizations of a sequence of $n$ matrices by $P(n)$. When $n$ = 1, we have just one matrix and therefore only one way to fully parenthesize the matrix product. When $n$ $\geq$ 2, a fully parenthesized matrix product is the product of two fully parenthesized matrix subproducts, and the split between the two subproducts may occur between the $k$th and ($k$ + 1)st matrices for any $k$ = 1, 2, ..., $n$ - 1.

what I don't understand is the the part about the split? what exactly does it mean to split the two subproducts?

$\endgroup$

2 Answers 2

3
$\begingroup$

The split in a product is between the two outermost pairs of parantheses. For example, in $((a*b)*(c*d))*(e*f)$, the split is between the $d$ and $e$ because the last multiplication that is performed is between the results of the products $abcd$ and $ef$. The split tells you where the last multiplication is performed and let’s you decompose the problem into two subproblems.

$\endgroup$
1
  • $\begingroup$ I understand, thank you. $\endgroup$
    – beginwithc
    Jun 9, 2022 at 18:54
4
$\begingroup$

Suppose you have $n$ matrices $M_1, M_2, …, M_n$.

The product of all matrices is $M_1\times M_2\times…\times M_n$ and since the matrix product is associative, there is no need for parentheses from a mathematical point of view.

However, from a complexity perspective, the product may not takes the same amount of computation time if you compute $M_1\times (M_2\times … \times M_n)$ or $(M_1\times M_2)\times (M_3\times…\times M_n)$ and so on.

For example, using the naive matrix multiplication algorithm, if $n = 3$ and the dimensions of $M_1$ are $10 \times 100$, the dimensions of $M_2$ are $100\times 5$ and the dimensions of $M_3$ are $5\times 2$, then computing $M_1\times (M_2\times M_3)$ uses $100\times 5 \times 2 + 10 \times 100 \times 2 = 3000$ scalar multiplications, but computing $(M_1\times M_2)\times M_3$ uses $10\times 100 \times 5 + 10 \times 5 \times 2 = 5100$ scalar multiplications.

The split the book is talking about is about the position of the parentheses in the computation, separating the computation of $n$ matrices into the product of two matrices, the first one being the result of $M_1\times … \times M_k$ and the second one of $M_{k+1}\times …\times M_n$, for a certain $k\in \{1, …, n-1\}$.

$\endgroup$
1
  • $\begingroup$ I understand, thank you. $\endgroup$
    – beginwithc
    Jun 9, 2022 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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