Re:Dynamic Programming: Chain Matrix Multiplication
by HalcyonicStorm on Thursday January 31, 2013 @11:48AM
(#5145837)
Thanks, I added that because the slideshow was rough if not viewed with a wide enough screen resolution. As for the left to right vs right to left, you can't fill the sub-diagonal entries because those switch the order of multiplying the matrices and will give you a different answer, ie. AxB != BxA. As for the terrible spelling, there's a reason why I do math :P
I didn't understand the statement that
(from Preliminaries 3: Cost table). Matrix multiplication is associative, so can be grouped as you like, and then reduced 'left to right' or 'right to left'. I think the relevant point is that the cost is symmetric, in the sense that the two orders of reduction give the same cost; so there's no need to fill in the sub-diagonal entries. Is that correct?Finally, I'm sorry to have to nit-pick that the plural of 'matrix' is 'matrices' (just one 'i'). At least you didn't use singular 'matrice'. :-)