Matrix Chain Multiplication

[madmax2006]

I'm just not getting something here, and I have no idea where I'm lost, and I don't know what questions to ask. I'm getting a bit frustrated, so please, take it easy on me.

I have an algorithm that spits out the most efficient way to multiply 4 matrices.

For instance, if I want to multiply A1, A2, A3, A4, it will tell me to multiply them in the order A1(A2A3(A4)) - A2xA3 = B. BxA4 = C, A1xC = D.

It also gives me 2 matrices, 1 filled with 0's, 1's, 2's, and 3's, the other filled with numbers that can get I don't know how big, and 0's.

I think this is where my problem is. I don't know what these matrices are for, but I think it has to do with something similar to what's on top of page 19 of a page I found online:

http://www.cs.sunysb.edu/~jgao/CSE54...d-mount-DP.pdf

The reason I need to know what these matrices are for, is so I can write an algorithm that actually multiplies these together. If you think I should go over to a math forum, I will.

If you can offer any help, I would greatly appreciate it, thanks.

[tabstop]

These matrices would appear to be irrelevant to actually multiplying the matrices together, IF they actually are the matrices you think they are on page 19 -- they're just the scratch work to figure out what the optimal order is (i.e., those numbers appear to be operation counts, or something similar). Once you have the optimal order, you just multiply matrices in the ordinary way.

[madmax2006]

I assume you mean - once I have the order (A1(A2A3))A4 that I would multiply A2xA3, then that product by A1, and that product by A4. That's my problem, I'm not sure how to implement it that way. I already have a multiplication algorithm written.

I'll try to explain how I have this thing set up.

A1 - 4 x 1
A2 - 1 x 3
A3 - 3 x 2
A4 - 2 x 4

We have to put these in an array P as follows:

P(0) = a1->row
P(1) = a2->row
P(2) = a3->row
P(3) = a4->row
P(4) = a4->column

P(0) = 4
P(1) = 1
P(2) = 3
P(3) = 2
P(4) = 4

The array is passed to a function similar to the pseudo-wikipedia code.

It doesn't actually sort the matrices or anything, it just tells you the order. (Instructions per professor).

Now we have to write the code to actually multiply the matrices in the order of the function that we just wrote (facepalm). This is where I'm having a problem. We end up getting 2 matrices that have numbers like so:

0 0 0 0 0
0 0 1 1 1
0 0 0 2 3
0 0 0 0 3
0 0 0 0 0


0 0 0 0 0
0 0 12 14 30
0 0 0 6 14
0 0 0 0 24
0 0 0 0 0

Notice how these are similar to that "stuff" at the top of page 19?

----1
--1--3
1--2--3

I figured that it was related somehow.

I'm open to any ideas though - since our professor didn't provide anything that helps (I know I should come up with the algorithm, but I've got nothing).

[tabstop]

So did you read the bit about "extracting the sequence"? The split to multiply from i to j happens at s[i,j]. So in this example to multiply A1 through A4, we look at s[1][4] = 1, so the left side is A1 through A1 (which is just A1) and the right side is A2 through A4 (which we call recursively). To multiply A2 through A4, we look at s[2][4] = 2, so the split is at 2. Etc.

[madmax2006]

And yes, I've been reading it over & over since you posted it.../facepalm

I'm still not getting it, do you think you could explain a bit more about how to tell where the split is? Am I understanding what you mean about s[1][4](below)? Sorry if I'm frustrating you.

0 0 0 0 0
0 0 1 2 1
0 0 0 2 2
0 0 0 0 3
0 0 0 0 0
s[1][4] = 1
s[2][4] = 2

0 0 0 0 0
0 0 1 1 3
0 0 0 2 3
0 0 0 0 3
0 0 0 0 0
s[1][4] = 3
s[2][4] = 3

0 0 0 0 0
0 0 1 1 1
0 0 0 2 3
0 0 0 0 3
0 0 0 0 0
s[1][4] = 1
s[2][4] = 3

[tabstop]

Those are the values out of the matrix, yes. Note that in the second example, s[2][4] is irrelevant to the actual answer: since the split is at 3, you will have to do A1 through A3 and A4 last.