Question

Derive the principle of optimality for multiplication of matrix chain

Answer 1

Answer:

Dynamic programming.

Step-by-step explanation:

Multiplication of matrix chain is an optimization problem. Here the goal is find the most efficient way to multiply the matrices. Matrix multiplication is associative. The problem is to find the way of matrix multiplication which involves less and easy arithmetic operations. If each way of multiplication of matrix is verified, it would take a long time and the process will be very slow when there are many matrices involved.

The solution to this is breaking up the problem into smaller sets of related matrices, so that solutions of sub problems can be reused.

The dynamic programming algorithm is recursive and is as follows :

1. Split the given matrix expression in to two sub expressions.

2. Calculate the minimum cost of multiplying each sub sequence.

3. Add the costs together, to find it for the whole expression.

4. Repeat the same with the sub sequences and find the minimum cost of computation.

The results of each stage are stored so that they can be reused.

Multiplying of two matrices involves the minimum cost as there is only one way to do it. So, the sub sequences can be split, until a 2 are left.