9. IMPLEMENTATION OF MATRIX CHAIN MULTIPLICATION
AIM:
To write a java
program to implement Matrix Chain Multiplication.
ALGORITHM:
- A chain of matrices to be multiplied is given as input.
- For a sequence A1,A2,A3,A4 of 4 matrices, there are 5 different orderings=5 different parethesization.
i)
(A1,(A2(A3
A4)))
ii)
(A1((A2
A3)A4))
iii)
((A1
A2)(A3 A4))
iv)
((A1(A2
A3))A4)
v)
(((A1
A2)A3)A4)
- Matrix_Multiply(A,B)
If coloumns[A]!=rows[B]
Then error “incomplete dimensions”
Else for i <- 1 to rows[A]
Do for j <- 1 to columns[B]
Do c[I,j] <- 0
For k<- 1 to
columns[A]
Do
c[i,j]=C[i,j]+A[i,k]+B[i,j]
Return c
- A parenthesizing of the chain of the matrices is obtained as output.
PROGRAM :
public class
MatrixChainMulti
{
void matrixchain(int
a[])
{
int q;
int n=a.length;
int m[][]=new
int[n][n];
int s[][]=new
int[n][n];
for (int
i=1;i<n;i++)
m[i][i]=0;
for (int
l=2;l<n;l++) //l is the length
{
for(int i=1
;i<n-l+1;i++)
{
int j=i+l-1;
m[i][j]=Integer.MAX_VALUE;
for (int k=i
;k<=j-1;k++)
{
q=m[i][k]+m[k+1][j]+a[i-1]*a[k]*a[j];
if(q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
}
}
for(int
i=0;i<n;i++)
{
for(int
j=0;j<n;j++)
System.out.print(m[i][j]+"
");
System.out.println();
}
print_optimal(s,1,6);
}
void
print_optimal(int s[][],int i,int j)
{
if (i==j)
System.out.print("A"+i);
else
{
System.out.print("(");
print_optimal(s,i,s[i][j]);
print_optimal(s,s[i][j]+1,j);
System.out.print(")");
}
}
public static void
main(String args[])
{
int a[]={30, 35, 15,
5, 10, 20, 25};//A1:-30x35, A2:- 35x15, A3:- 15x5, A4:- 5x10 , A5:- 10x20, A6:-
20x25
MatrixChainMulti
n=new MatrixChainMulti();
n.matrixchain(a);
}
}