Optimal Matrix Multiplication - 2

Given two matrices A and B, matrix C = AB can be computed using the standard rules of matrix multiplication:

The number of columns in matrix A must be equal to the number of rows in matrix B. Let matrix A have size m \times n and matrix B have size n \times p. Then, matrix C will have size m \times p and to compute C you need to perform m \times n \times p multiplications.

For example, if A has size 10 \times 20, and B has size 20 \times 15, then 10 \times 20 \times 15 = 3000 multiplications are needed to compute C.

Multiplication of several matrices can be done in different ways. For example, if we have matrices X, Y, and Z, the product XYZ can be computed either as $(XY)Z$ or as $X(YZ)$. Suppose X has size 5 \times 10, Y has size 10 \times 20, and Z has size 20 \times 35.

Let's calculate the number of multiplications required for each approach:

$(XY)Z$

• 5 \times 20 \times 10 = 1000 multiplications to determine $(XY)$, which will be 5 \times 20.

• Then 5 \times 35 \times 20 = 3500 multiplications to compute the final result.

• Total: $4500$ multiplications.

$X(YZ)$

• 10 \times 35 \times 20 = 7000 multiplications to determine $(YZ)$, which will be 10 \times 35.

• Then 5 \times 35 \times 10 = 1750 multiplications to compute the final result.

• Total: $8750$ multiplications.

It is clear that computing $(XY)Z$ requires fewer multiplications.

Given a sequence of matrices to be multiplied, determine the optimal order of multiplication. The optimal order is the sequence that minimizes the total number of scalar multiplications.