Matrix Chain Multiplication


Matrix Chain Multiplication

  • Matrix chain multiplication (or Matrix Chain Ordering Problem, MCOP) is an optimization problem that can be solved using dynamic programming.
  • Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices.
  • The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved.
  • Here are many options because matrix multiplication is associative. In other words, no matter how the product is parenthesized, the result obtained will remain the same. For example, for four matrices A, B, C, and D, we would have:

((AB)C)D = ((A(BC))D) = (AB)(CD) = A((BC)D) = A(B(CD))
Matrix Chain Multiplication

Example of Matrix Chain Multiplication


Example:
Sequence {4, 10, 3, 12, 20, and 7}. The matrices have size 4 x 10, 10 x 3, 3 x 12, 12 x 20, 20 x 7. We need to compute M [i,j], 0 ≤ i, j≤ 5.
We know M [i, i] = 0 for all i.
Matrix Chain Multiplication
Matrix Chain Multiplication

Here P0 to P5 are Position and M1 to M5 are matrix of size (pi to pi-1) 
On the basis of sequence, we make a formula
Matrix Chain Multiplication

In Dynamic Programming, initialization of every method done by '0'.So we initialize it by '0'.It will sort out diagonally.
We have to sort out all the combination but the minimum output combination is taken into consideration.
Matrix Chain Multiplication
Matrix Chain Multiplication

Pseudo code

Matrix Chain Multiplication


Popular posts from this blog

C Program for SCAN Disk Scheduling Algorithm | C Programming

Image
Introduction to SCAN disk scheduling :                    In the SCAN algorithm, the disk arm starts at one end of the disk and moves toward the other end, servicing requests as it reaches each cylinder, until it gets to the other end of the disk. At the other end, the direction of the head movement is reversed, and servicing continues. The head continuously scans back and forth across the disk. The SCAN algorithm is sometimes called the elevator algorithm, since the disk arm behaves just like an elevator in a building, first servicing all the requests going up and then reversing to service requests the other way.
Read more

C program to Find Cartesian Product of Two Sets | C programming

Image
C program to find the Cartesian Product of two sets   Cartesian product  is a mathematical operation that returns a set (or  product set  or simply  product ) from multiple sets. That is, for sets  A  and  B , the Cartesian product  A  ×  B  is the set of all ordered pairs  ( a ,  b )  where  a  ∈  A  and  b  ∈  B . Products can be specified using set-builder notation, e.g. {\displaystyle A\times B=\{\,(a,b)\mid a\in A\ {\mbox{ and }}\ b\in B\,\}.}
Read more

C Program To Check The String Is Valid Identifier Or Not | C Programming

Image
C Program To Check The String Is Valid Identifier Or Not #include <stdio.h> #include <conio.h> #include <string.h> int main () { char string [ 25 ]; int count= 0 ,flag; printf ( "Enter any string: " ); gets (string); if ( ( string [ 0 ]>= 'a' && string [ 0 ]<= 'z' )||( string [ 0 ]>= 'A' && string [ 0 ]<= 'Z' )||( string [ 0 ]== '_' )) {     for ( int i= 1 ;i<= strlen (string);i++)     {         if (( string [i]>= 'a' && string [i]<= 'z' )||( string [i]>= 'A' && string [i]<= 'Z' )||( string [i]>= '0' && string [i]<= '9' )||( string [i]== '-' ))     {     count++;     }        }     if (count== strlen (string))     {       flag= 0 ;     } } else {     flag= 1 ; } if (flag== 1 )     printf ( " %s is not valid identifier" ,string); else     printf ( " %s is valid ident
Read more