Editing Matrix chain multiplication (section)

=== Hu &amp; Shing ===
An algorithm published by [[T. C. Hu]] and M.-T. Shing achieves ''O''(''n''&nbsp;log&nbsp;''n'') [[computational complexity]].<ref>
{{cite journal
  | last1 = Hu
  | first1 = T. C. | author1-link = T. C. Hu
  | last2 = Shing
  | first2 = M.-T.
  | title = Computation of Matrix Chain Products, Part I
  | journal = SIAM Journal on Computing
  | volume = 11
  | issue = 2
  | pages = 362–373
  | year = 1982
  | url = http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/0211028.pdf
  | issn = 0097-5397
  | doi=10.1137/0211028
| citeseerx = 10.1.1.695.2923
  }}
</ref><ref name=HuPartII>
{{cite journal
   | last1 = Hu
  | first1 = T. C. | author1-link = T. C. Hu
  | last2 = Shing
  | first2 = M.-T.
  | title = Computation of Matrix Chain Products, Part II
  | journal = SIAM Journal on Computing
  | volume = 13
  | issue = 2
  | pages = 228–251
  | year = 1984
  | url = http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/0213017.pdf
  | issn = 0097-5397
  | doi=10.1137/0213017
| citeseerx = 10.1.1.695.4875
  }}
</ref><ref name="Czumaj">
{{cite journal
  | first = Czumaj
  | last = Artur
  | title = Very Fast Approximation of the Matrix Chain Product Problem
  | journal = Journal of Algorithms
  | volume = 21
  | pages = 71–79
  | year = 1996
  | url = https://pdfs.semanticscholar.org/e8b8/40a921f7967b30ac161b3dd9654b27998ddb.pdf
  | archive-url = https://web.archive.org/web/20180727180949/https://pdfs.semanticscholar.org/e8b8/40a921f7967b30ac161b3dd9654b27998ddb.pdf
  | url-status = dead
  | archive-date = 2018-07-27
  | doi = 10.1006/jagm.1996.0037
  | citeseerx = 10.1.1.218.8168
  | s2cid = 2818053
 }}
</ref>
They showed how the matrix chain multiplication problem can be transformed (or [[Reduction (complexity)|reduced]]) into the problem of [[polygon triangulation|triangulation]] of a [[regular polygon]].  The polygon is oriented such that there is a horizontal bottom side, called the base, which represents the final result. The other ''n'' sides of the polygon, in the clockwise direction, represent the matrices. The vertices on each end of a side are the dimensions of the matrix represented by that side.  With ''n'' matrices in the multiplication chain there are ''n''−1 [[binary operation]]s and ''C''<sub>''n''−1</sub> ways of placing parentheses, where ''C''<sub>''n''−1</sub> is the (''n''−1)-th [[Catalan number]]. The algorithm exploits that there are also ''C''<sub>''n''−1</sub> possible triangulations of a polygon with ''n''+1 sides.

This image illustrates possible triangulations of a regular [[hexagon]].  These correspond to the different ways that parentheses can be placed to order the multiplications for a product of 5 matrices.
[[Image:Catalan-Hexagons-example.svg|400px|center]]

For the example below, there are four sides: A, B, C and the final result ABC.  A is a 10×30 matrix, B is a 30×5 matrix, C is a 5×60 matrix, and the final result is a 10×60 matrix. The regular polygon for this example is a 4-gon, i.e. a square:
[[File:Matrix chain multiplication polygon example.svg|125px|center]]

The matrix product AB is a 10x5 matrix and BC is a 30x60 matrix. The two possible triangulations in this example are:
<gallery mode="packed">
File:Matrix chain multiplication polygon example AB.svg|alt=(AB)C|Polygon representation of (AB)C
File:Matrix chain multiplication polygon example BC.svg|alt=A(BC)|Polygon representation of A(BC)
</gallery>

The cost of a single triangle in terms of the number of multiplications needed is the product of its vertices. The total cost of a particular triangulation of the polygon is the sum of the costs of all its triangles:

:(''AB'')''C'': (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 multiplications
:''A''(''BC''): (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 multiplications

Hu & Shing developed an algorithm that finds an optimum solution for the minimum cost partition problem in ''O''(''n''&nbsp;log&nbsp;''n'') time. Their proof of correctness of the algorithm relies on "Lemma 1" proved in a 1981 technical report and omitted from the published paper.<ref>
{{cite tech report
  | last1 = Hu
  | first1 = TC
  | last2 = Shing
  | first2 = MT
  | title = Computation of Matrix Chain Products, Part I, Part II
  | number = STAN-CS-TR-81-875
  | institution = Stanford University, Department of Computer Science
  | year = 1981
  | url = http://infolab.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf#page=31
  | at=Part II, page 3
}}
</ref><ref name=HuPartII/> The technical report's proof of the lemma is incorrect, but Shing has presented a corrected proof.<ref name=Schwartz>{{cite journal |last1=Schwartz |first1=Oded |last2=Weiss |first2=Elad |title=Revisiting ''Computation of Matrix Chain Products'' |journal=SIAM Journal on Computing |date=January 2019 |volume=48 |issue=5 |pages=1481–1486 |doi=10.1137/18m1195401|s2cid=203009883 }}</ref>