Talk:Matrix chain multiplication

cost of string concatenation

I think it's not justified to say that string concat is O(n+m), one has to distinguish

• the search for the end token (in O(n), but only READ), and
• the creation of the new string (requiring

• memory allocation (which might be more expensive than all the rest, depending on implementation (default MEM_CLEAR or so))
• COPYING of the first and then the second string (READ + WRITE in another memory segment, O(n+m) operations)

On the other hand, if one uses reference counting and allows for segmented string storage, then the concatenation takes virtually no time.

Concerning "memoization", why the heck did this guy not call it memorization ??? (Or memo'ization ?)

And finally, I would be astonished if there was no better ("local") method for optimizing this matrix problem, rather than checking all possible combinations... I'll think about this... MFH 13:43, 24 Mar 2005 (UTC)

Greedy algorithms don't work well for this problem, because locally optimal solutions may turn out to force a globally poor solution — not that there aren't decent approximation algorithms based on heuristics. If you click on the memoization link, you'll discover that this is not a misspelling, like everyone always assumes (I wish they'd pick a less confusing word). You're right that different approaches to string concatenation take very different amounts of time. This is mostly irrelevent, since the technique works with any cost function, but the specific cost I give is for a C strcat() call without any reallocation (it's assumed sufficient space is available after the first string). Deco 23:15, 24 Mar 2005 (UTC)

Ambiguity due to using variable 'l'

I had a hard time understanding the pseudocode because of the variable 'l', which is defined in the outer-most main loop. The statements "n-l+1" and "i+l-1" appeared to me as "n-1+1" and "i+1-1". (I could not distinguish the 'l' variable from the '1'. In anti-aliased Courier New font, the difference was very small for my eye to see.)

I first thought that these statements may be intended by the writer to indicate that 1 was removed for some reason and added for a different reason (as when a loop is said to run (n-1)+1 times). I then couldn't figure out the reasons, and it took me quite some time to understand that it is an 'l'. (Actually I was already writing in the discussion page to ask how the algorithm could be like that - it would be definitely wrong.)

I wish you could take this into consideration (in this and other articles), and use a variable other than 'l'. In this specific algorithm, the name "len" may be good.

Thanks. --Hosam Aly 19:39, 7 January 2007 (UTC)

No reference to much more efficient ways to solve the problem

Although this problem is often quoted as a good way to teach dynamic programming, the resulting O(n^3) time complexity is very poor compared to the best known. O(n log n) time can be achieved by observing that the problem can be reduced to that of finding the minimum weight triangulation of a polygon.

87.194.206.189 (talk) 13:06, 21 December 2008 (UTC)

Agreed, I have added a stub for this. kostmo (talk) 22:02, 4 April 2009 (UTC)

final order of the matrix multiplication

PRINT-OPTIMAL-PARENS(s, i, j)

if i=j

  print ′′A′′i ;

else

   print ”(”;
   PRINT-OPTIMAL-PARENS(s, i, s[i, j])
   PRINT-OPTIMAL-PARENS(s, s[i, j]+1, j)
   print ”)”

this is the pseudocode to find final order of the matrix multiplication but i am having problem in solving the problem manually —Preceding unsigned comment added by Pathakamit90 (talk • contribs) 02:19, 14 February 2010 (UTC)

setup

This page needs a lot more setup. It might help to say things like multpling an nxm by a mxk n*m*k, and that order matters (before getting into the example) and that this is a common problem. 0¹⁸ (talk) 19:18, 11 October 2011 (UTC)

Other research

The following research may be used in support of this page (SIAM as well as Hu and Shing apparently have been considered reliable enough for wikipedia for years):

• T. C. Hu and M. T. Shing, Some Theorems about Matrix Multiplication, Proceedings of the 21st Annual IEEE Symposium on the Foundations of Computer Science, 28-35, 1980.
• T. C. Hu and M. T. Shing, An O(n) Algorithm to Find a Near Optimum Partition of a Convex Polygon, Journal of Algorithms, 2, 122-138, 1981.
• T. C. Hu, Combinatorial Algorithms, Addison-Wesley, New York, 1982
• F. F. Yao, Speed-Up in Dynamic Programming, SIAM Journal on Algebraic and Discrete Methods, 3(4), 532-540, 1982
• P. Ramanan, A New Lower Bound Technique and its Application: Tight Lower Bounds for a Polygon Triangulation Problem, SIAM Journal on Computing, 23(4), 834-851, 1994.

Also, these provide enough information to write a History section about the Matrix Chain Ordering Problem. R.J.C. van Haaften (talk) 21:57, 23 January 2015 (UTC)

This seems to be the place to provisionally plug

• Daxin ZHU, Yingjie WU, and Xiaodong WANG: "An Efficient Algorithm for Chain Multiplication of Dense Matrices and Its Computer Implementation", Journal of Computational Information Systems 10: 10 (2014) 4299–4306, O(nlogn), claims to be simpler (and faster) than Hu/Shing.

For lack of reachability of JofCIS and fear of disappearance:

Algorithm Unimodal()
Initialize()
cost(rn-2) ← w(vt-1)w(vt)w(vt+1)
crit(rn-2) ← cost(rn-2) ⁄ W(rn-2)-w(vt-1)w(vt+1)
for i ← n − 3 downto 0 do
S.push(ri+1)
u ← {ri-1(1),ri-1(2)}−{ri-1(1),ri-1(2)}∩{ri(1),ri(2)}
v ← {ri(1),ri(2)}−{ri-1(1),ri-1(2)}∩{ri(1),ri(2)}
while S not empty and w(u) ≤ crit(S.top) do
S.pop()
ra ← S.top
cost(ri) ← cost(ra) + w(u)×(W(ri) − W(ra) + w(ra(1))w(ra(2)) − w(u)w(v))
while S not empty and f(crit(S.top)) > 0 do
S.pop()
rb ← S.top
crit(ri) = cost(ri)-cost(rb)) ⁄ (W(ri)-W(rb)-w(ri(1))w(ri(2))
while S not empty and crit(ri) ≤ crit(S.top) do
S.pop()

Algorithm Triangulation()
Initialize()
post-order list of the horizontal arcs:
rn-2,rn-3,··· ,r0
cost(rn-2) ← w(vt-1)w(vt)w(vt+1)
crit(rn-2) ← cost(rn−2) ⁄ (W(rn−2)-w(vt−1)w(vt+1)
for i ← n − 3 downto 0 do
S.push(ri+1)
P Q.push(ri+1)
if Bridge(ri) then
rp ← Left(ri)
rq ← right(ri)
cumucost(ri) ← cost(rp) + cost(rq)
cumuw(ri) ← W(rp) + W(rq) − w(rp(1))w(rp(2)) − w(rq(1))w(rq(2))
Merge(rp,rq)
u ← {ri-1(1),ri-1(2)}−{ri-1(1),ri-1(2)}∩{ri(1),ri(2)}
v ← {ri(1),ri(2)}−{ri-1(1),ri-1(2)}∩{ri(1),ri(2)}
rp ← P Q.max
while w(u) < crit(rp) do
S.delete(rp)
P Q.delete(rp)
cumucost(ri) ← cumucost(ri) − cost(rp) + cumucost(rp)
cumuw(ri) ← cumuw(ri) − W(rp) + w(rp(1))w(rp(2)) + cumuw(rp)
rp ← P Q.max
cost(ri) ← cumucost(ri) + w(u)(W(ri) − cumuw(ri) − w(u)w(v))
rp ← P Q.max
while f(crit(rp)) < 0 do
S.delete(rp)
P Q.delete(rp)
cumucost(ri) ← cumucost(ri) − cost(rp) + cumucost(rp)
cumuw(ri) ← cumuw(ri) − W(rp) + w(rp(1))w(rp(2)) + cumuw(rp)
rp ← P Q.max
crit(ri) ← cost(ri)-cumucost(ri) ⁄ W(ri)-cumuw(ri)-w(ri(1))w(ri(2))
rp ← P Q.max
while crit(ri) ≤ crit(rp) do
P Q.delete(rp)
rp ← P Q.max
Algorithm Triangulation() requires O(nlog m) time and O(n) space in the worst case.

188.100.196.116 (talk) 01:11, 31 January 2016 (UTC)

Well, the conference paper is on IEEE and is easily accessible if you can get past the paywall. I've added it to the article. But it doesn't have the triangulation algorithm written out. There's an entry on ResearchGate with the DOI 10.12733/jcis10313 but unfortunately the DOI doesn't resolve and the JofCIS website [1] only lists the first four papers. So thanks! --Mathnerd314159 (talk) 00:47, 23 April 2022 (UTC)

Solving similar problems

If you know of algorithms for these problems would you add them to the article?

Problem #1: When the product of several matrices ABCDE is square, its matrix trace Tr(ABCDE) can be computed faster than with a two step process of first computing the product of the matrices P=ABCDE and then computing the trace of that product Tr(P). This arises for two reasons:

1. Only the diagonal entries of P need to be computed. For instance if the last two matrices to be multiplied are (ABC), which is v₀×v₃, and (DE), which is v₃×v₅, with v₀=v₅, then the trace of that product can be computed in time O(v₀v₃) rather than in time O(v₀v₃v₅).
2. We can exploit that the matrix trace is preserved under cyclic permutations. That is, Tr(ABCDE) = Tr(BCDEA) = Tr(CDEAB) = Tr(DEABC) = Tr(EABCD).

Is there an efficient algorithm that simultaneously finds the cyclic permutation and order of matrix multiplications to most efficiently compute Tr(ABCDE)?

Problem #2: When the product of several matrices ABCDE is square, the matrix determinant det(I+ABCDE) can be computed. We can exploit cyclic permutations as before, using that det(I+ABCDE) = det(I+BCDEA) = det(I+CDEAB) = det(I+DEABC) = det(I+EABCD). Instead of the time savings with the last matrix multiplication that we had for the matrix trace, we have an extra cost, that of computing the determinant, which depends upon the matrix dimensions of whichever of I+ABCDE, I+BCDEA, I+CDEAB, I+DEABC, I+EABCD we are computing the determinant of in the last step. Is there an efficient algorithm that simultaneously finds the cyclic permutation and order of matrix multiplications to most efficiently compute det(I+ABCDE)? Leegrc (talk) 13:19, 28 January 2015 (UTC)

External links modified (January 2018)

Hello fellow Wikipedians,

I have just modified one external link on Matrix chain multiplication. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20110722132611/http://ccs.korea.ac.kr/pds/tpds03.pdf to http://ccs.korea.ac.kr/pds/tpds03.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 15:40, 21 January 2018 (UTC)

Removal of reference

Recently, the reference to the original Stanford article was removed. The removed reference contains proofs omitted in the published journal version. The journal version explicitly refers to the Stanford article for details as reference 9 (part 1) and reference 7 (part 2) respectively. That's why I prefer to keep the Stanford article as well.

On the other hand, though the Stanford article is complete, the typesetting of the journal is a lot better, so I prefer to keep the journal versions as well for readability. — Preceding unsigned comment added by R.J.C.vanHaaften (talk • contribs) 10:43, 28 July 2018 (UTC)

Wikipedia policy is to refer only to WP:reliable sources. Generally, technical reports are not considered as reliable sources. Here, referring to the technical report could make sense if the article would mention a detail that is in the technical report and not in the published article. This is not the case. Thus there is no reason for citing the technical report. D.Lazard (talk) 11:56, 28 July 2018 (UTC)

I agree to the policy you mention, but I don't understand your assessment. The published article refers to the report, omitting details explicitly (Lemma 1: "Proof. Omitted. See [7] for details."). That's why I retained the report, though I agree on preferring the published article. R.J.C.vanHaaften (talk) 16:33, 28 July 2018 (UTC)

The published article suffices for a reader who want not knowing all details. For a reader who want to know all details, it is better to read first the published article, and then follow the links there to the technical report. So, in all cases there is no need to refer, in WP, to the technical report. D.Lazard (talk) 17:32, 28 July 2018 (UTC)

Well in this case it turns out one of the omitted proofs is wrong. So I've added the TR back. --Mathnerd314159 (talk) 00:30, 23 April 2022 (UTC)