Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Matrix Chain Multiplication: Optimal way of multiplying

  1. Feb 26, 2017 #1
    Hi,

    I am studying Matrix chain Multiplication to find out the optimal way of multiplying a series of matrices so that we can reduce the number of multiplications. I have got this example from the book which multiplies the matrices having dimensions given below:

    A1 30 * 35

    A2 32 * 15

    A3 15 * 5

    A4 5 * 10

    A5 10 * 20

    A6 20 * 25

    From these matrices, it creates the 2 tables:

    M TABLE.jpg

    s table.jpg
    The algorithm is given below:

    MTM(A, s, I, j)

    If j> i

    Then Xß MCM(A, s, I, s[I,j])

    Y ß MCM(A, s, s[I,j] + 1, j)

    return MCM (X, Y)

    else return Ai

    They are invoking the algorithm by:

    MCM(A, s, 1, 6)

    Can some body guide me what is the value of A & s?
    After that i want to find out the best way of ordering these matrices for multiplication. Some body please guide me.
    Zulfi.
     
  2. jcsd
  3. Feb 26, 2017 #2
    I guess the book should explain this?

    If I'm reading the algorithm correctly, it multiplies t=A1*A2, t=t*A3, s=A5*A6, s=A4*s, t=t*s, return t. This seems to comply with the intuitive idea of picking the longest "edge" available:
    first 35 between A1 and A2,
    then 20 between A5 and A6,
    then 15 between (A1*A2) and A3,
    then 10 between A4 and (A5*A6),
    and last 5 between (A1*A2*A3) and (A4*A5*A6).
    The s-table is a way to drive the calculation, even though it seems a bit complicated. The m-table is probably used to fill in the s-table, and that should be explained in the book you're reading.

    Just a side note, if you want to get anywhere in programming, you *absolutely can not* afford typing errors. I is not i, A is not m, 32 is not 35, and MCM is not MTM.
     
  4. Mar 3, 2017 #3
    Hi,
    I am correcting my algorithm. I cant find edit option:
    1. MCM(A, s, i, j)
    2. if j> i
    3. then X= MCM(A, s, i, s[i,j])
    4. Y = MCM(A, s, s[i,j] + 1, j)
    5. return MCM (X, Y)
    6. else return Ai

    Kindly tell me how to evaluate this algorithm.

    Zulfi.
     
  5. Mar 3, 2017 #4

    Mark44

    Staff: Mentor

    You don't "evaluate" an algorithm -- you (or the computer) perform the steps in the algorithm.
    Step 1. What does MCM(A, s, i, j) mean? What action is performed by this step? What are A and s, and what are the values of i and j? Are A and s two-dimensional arrays?
    Step 2. Are the values of i and j known? If not, how can anyone know whether j > i or i < j or i == j?
    Step 5. What does MCM(X, Y) mean? What are X and Y? In steps 1, 3, and 4, MCM takes four arguments. In this step there are only two arguments.
    Step 6. What is Ai?
     
  6. Mar 3, 2017 #5
    Hi,
    Thanks for taking interest in my problem.
    MCM means Matrix Chain Multiplication & 4 arguments are passed to this algorithm
    <
    You don't "evaluate" an algorithm -- you (or the computer) perform the steps in the algorithm.
    >
    I have to evaluate the value return by algorithm by tracing the steps mentioned in it. Its a recursive algorithm. I am doing some tracing work but it I get confused because of the two recursive calls & X & Y will get what value returned by the recursive function.


    <
    Are the values of i and j known? If not, how can anyone know whether j > i or i < j or i == j?

    >
    Yes I have to call: MCM(A,s,1,6), A & s are shown in the figure which are two tables accessed by i & j
    Therefore i=1 & j=6
    <
    What does MCM(X, Y) mean? What are X and Y? > Sorry this is again a mistake,
    1. MCM(A, s, i, j)
    2. if j> i
    3. then X= MCM(A, s, i, s[i,j])
    4. Y = MCM(A, s, s[i,j] + 1, j)
    5. return MatrixMultiply (X, Y)
    6. else return Ai

    This means X & Y are matrices & i have shown their rows & columns above. Again:
    A1 30 * 35
    A2 35 * 15
    A3 15 * 5
    A4 5 * 10
    A5 10 * 20
    A6 20 * 25


    Thus i want to a know a better method or technique for evaluating (i.e. to find out the value returned by) this recursive function.

    Zulfi.
     
  7. Mar 3, 2017 #6
    Hi,
    I mentioned the invoking statement in my first post also:
    <
    They are invoking the algorithm by:

    MCM(A, s, 1, 6)

    Can some body guide me what is the value of A & s?
    After that i want to find out the best way of ordering these matrices for multiplication. Some body please guide me.
    Zulfi.
    >

    Zulfi.
     
  8. Mar 3, 2017 #7
    ##A## is an array of the input matrices. For example, A[3] is a matrix of 15*5 elements.
    ##s## is a 2-dimensional array, with values as given in the picture in your first post. The elements that are not shown, such as s[4,2], are not used by the algorithm, so the value of these elements is not important.
     
  9. Mar 4, 2017 #8
    Hi,
    My friend thanks for your reply.
    <A is an array of the input matrices. For example, A[3] is a matrix of 15*5 elements.>
    I don't think so because the book has shown the values of A1-A6 in terms of its dimensions. We have to use these dimensions to find out the optimal way of multiplying these matrices.
    <
    s is a 2-dimensional array, with values as given in the picture in your first post. The elements that are not shown, such as s[4,2], are not used by the algorithm, so the value of these elements is not important.>
    No my friend 's' table is very important. That's why book has shown it. I have Solved this problem using recursion tree. Thanks all.

    Zulfi.
     
  10. Mar 4, 2017 #9
    Hi,
    Sorry for wrongly correcting you. I agree with you.

    <A is an array of the input matrices. For example, A[3] is a matrix of 15*5 elements.>
    The above is correct. Dimensions are stored in another set of variables: p0 to p6 & this is mentioned in another algorithm which is used to create 'm' table.

    Thanks for your time.

    Zulfi.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Matrix Chain Multiplication: Optimal way of multiplying
  1. MadGraph optimization (Replies: 4)

Loading...