Matrix Chain Multiplication

This is a discussion on Matrix Chain Multiplication within the C Programming forums, part of the General Programming Boards category; I'm just not getting something here, and I have no idea where I'm lost, and I don't know what questions ...

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    68

    Matrix Chain Multiplication

    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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    68
    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).

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  5. #5
    Registered User
    Join Date
    Feb 2009
    Posts
    68
    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
    Last edited by madmax2006; 04-13-2010 at 07:39 PM.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 02:30 PM
  2. *operator overloading: scalar matrix multiplication
    By gemini_shooter in forum C++ Programming
    Replies: 4
    Last Post: 06-08-2009, 02:14 PM
  3. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 05:57 PM
  4. What is a matrix's purpose in OpenGL
    By jimboob in forum Game Programming
    Replies: 5
    Last Post: 11-14-2004, 12:19 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21