Note on Matrix Multiplication Question

[kris manohar]

Hey All,

The mmq ( Matrix Multiplication Question ) is worth 10 marks which is somewhere about what I got last time so I am thinking sweet can do one question in 50mins 

and do just as good....wonder what order that is...lols.

That thought aside. Please try an practice this question, yeah its 10marks but you really have to WORK for it.

By following the algorithm in the hand out he gave us you basically work out the diagonals.

Usually he asks to show working on how you go the table. So what I suggest is that for each entry you do something like this:

C[1 4]

r1    r2               r5                   //you can ignore these r's I just put them there so can work you the mpn value quickly

M1 | M2 M3 M4 = 0 + C[2 4 ] + r1*r2*r3 = whatever1

r1       r3  r3       r5                   

M1  M2 | M3 M4 = C[1 2] + C[3 4 ] + r1*r3*r5 = whatever2

r1              r4       r5                   

M1  M2  M3 | M4 = C[1 3] + 0 + r1*r4*r5 = whatever3

=> min(whatever1,whatever2,whatever3) = the ans for C[1 4]

Then move to the next entry. As you can see this will take a while. I usually draw the table first, fill in the 0's for the i = j stuff. Of course you will have to write out the r array so (labeling the entries 1 to n is not a bad idea either makes working out r1*3*r5 say easier).  Then start with D0 and move on showing the working for each entry similar to above. Other than this have to take your time multiplying. 

I suggest doing this question first since its worth the most marks. However its longer but does not require too much figuring out it usually only comes one way so some time is saved there. 

Humm... wonders if there is a dynamic programming solution to choosing the order in which to do questions in an exam? lolz

Kris

--
If you want it, then  go get it!

[Irwin Williams]

Here's the full algo btw:

#include <stdio.h>

main(){

int i, j, k, d, n=5;

int M[n+1][n+1];

int R[]={0,3,6,5,2,8,3};

for(i=1;i<=n;i++) M[i][i]=0;

for(d=1;d<n;d++){

  for(i=1; i<= n-d; i++){

    j=i+d;

    M[i][j]=9999;

    for(k=i+1; k<=j; k++){

      int temp = M[i][k-1]+M[k][j]+R[i]*R[k]*R[j+1];

       if(temp<M[i][j]){

        M[i][j]=temp;

        M[j][i]=k;

        }

    }

   }

}

//print output

for(i=1;i<=n;i++){

 printf("\n");

  for(j=1;j<=n;j++){

   printf("%d\t",M[i][j]);

   

}

}

system("pause");

--
Irwin Williams
785-1268
________________________
*I am a software solutions developer.*
Do you see a man skilled in his work?
He will serve before kings; he will not
serve before obscure men.
Proverbs 22:29

[Kyle E. deFreitas]

I also advise persons when doing this question to store the division point k in the lower half of the diagonal.

Its within the algorithm that Irwin has posted above, but people sometimes forget to put it in when they doing the calculation in the exam

regards

--
Kyle deFreitas
St Vincent and the Grenadines
Contact #: 1-784-454-4037
or
1-868-722-5346

[vramd...@gmail.com]

Hi Kyle,
I am seeing k being stored in the lower half of the matrix in Irwin's algorithm, but I am not sure why that is useful?
Can you say?

Thanks
Vincent

Sent from my BlackBerry® wireless device available from bmobile.

---

From: "Kyle E. deFreitas" <kyle.e.d...@gmail.com>

Sender: design-and-analy...@googlegroups.com

Date: Wed, 10 Nov 2010 10:55:20 -0400

To: <design-and-analy...@googlegroups.com>

ReplyTo: design-and-analy...@googlegroups.com

Subject: Re: Note on Matrix Multiplication Question

[Irwin Williams]

When you're printing, you'll know where exactly to split the array and so place the parameters

[Kyle E. deFreitas]

Yes well both when you printing

and also if you writing out the steps as he ask in most cases.

the k lets you know where to put the brackets

so for 

M1 M2 M3 M4 M5

if in your table you have 5,1 = 4

then you split the matrices as:

(M1 M2 M3) (M4 M5)

then you look in your table for how to divide matrices 1 - 3

the division point is stored at 3,1

so assuming 4,1 = 2

then the multiplication becomes

(M1)(M2 M3) (M4 M5)

if your table in 5,1 = 5 and 

then

(M1 M2 M3 M4) (M5)

if 4,1 = 4

(M1 M2 M3) (M4) (M5)

hope this sheds some light

regards

[Irwin Williams]

this sheds light.

[Vincent Ramdhanie]

AH! That sheds a lot of light. Thanks.

I think I am now confident about matrix chain multiplication so I hope it comes. Now on to the next topic...

On Wed, Nov 10, 2010 at 12:36 PM, Kyle E. deFreitas <kyle.e.d...@gmail.com> wrote:

[Vincent]

Here is my version of the Matrix Chain program written in Java.
Because Java arrays are indexed from 0 and these algorithms are
indexed from 1 I decided to simply declare c[6][6] when I need a 5 x 5
array and ignore the 0th row and column. It is easier than trying to
modify the algorithm to be indexed from 0.

/**
*
* @author vramdhanie
*/
public class Matrix {
public static void main(String args[]){
Matrix m = new Matrix();
m.process();
}

int c[][];
int r[] = {0, 5, 10, 4, 6, 10, 2};
int n;

public void process(){
c = new int[6][6];
n = 5;
doMatrix();
parenthesize(1, n);
print();
}

public void parenthesize(int i, int j){
if(i == j){
System.out.print(String.format("(M%d)", i));
}else{
if(j - i == 1){
System.out.print(String.format("(M%dM%d)", i, j));
}else{
System.out.print("(");
parenthesize(i, c[j][i] - 1);
parenthesize(c[j][i], j);
System.out.print(")");
}
}
}

public void print(){
System.out.println();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
System.out.print(c[i][j] + " ");
}
System.out.println();
}
}
public void doMatrix(){
for(int i = 1; i <= n; i++){
c[i][i] = 0;
}

for(int w = 1; w < n; w++){
for(int i = 1; i <= n - w; i++){
int j = w + i;
c[i][j] = Integer.MAX_VALUE;
for(int k = i + 1; k <= j; k++){
int q = c[i][k - 1] + c[k][j] + r[i] * r[k] * r[j
+ 1];
if(q < c[i][j]){
c[i][j] = q;
c[j][i] = k;
}
}
}
}

}
}