Chain matrix multiplication :-

 

-Chain matrix multiplication is an optimization problem in computer science that deals with finding the most efficient way to multiply a sequence of matrices together. This problem is also known as the Matrix Chain Multiplication Problem.

-Matrix Chain Multiplication Problem, involves finding the most efficient way to parenthesize a sequence of matrices to minimize the number of scalar multiplications needed.

-It's typically solved using dynamic programming, and the result is an optimal order for matrix multiplication.

-Ex.

Suppose you have the following sequence of matrices:

Matrix A: 10x30

Matrix B: 30x5

Matrix C: 5x60

Matrix D: 60x10

-To multiply these matrices, you can choose from various parenthesizations:

 

-Cost of (A*B) = (10 * 30 * 5) = 1500 scalar multiplications

-Cost of (B*C) = (30 * 5 * 60) = 9000 scalar multiplications

-Cost of (C*D) = (5 * 60 * 10) = 3000 scalar multiplications

-Cost of (A*B)*(C) = (1500 + (10*5*60)) = 9000 scalar multiplications

-Cost of (B)*(C*D) = (9000 + (30*60*10)) = 27000 scalar multiplications

-Cost of (A*(B*(C*D))) = 9000 + (10*30*10) = 21000 scalar multiplications

-In order to make minimal scalar multiplication we have to multiply (A*B) first then multiply (C*D) then multiply them both.