Editing Matrix chain multiplication (section)

== More efficient algorithms ==
There are algorithms that are more efficient than the ''O''(''n''<sup>3</sup>) dynamic programming algorithm, though they are more complex.

=== 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>

=== Other ''O''(''n''&nbsp;log&nbsp;''n'') algorithms ===

Wang, Zhu and Tian have published a simplified ''O''(''n''&nbsp;log&nbsp;''m'') algorithm, where ''n'' is the number of matrices in the chain and ''m'' is the number of local minimums in the dimension sequence of the given matrix chain.<ref>{{cite book |last1=Wang |first1=Xiaodong |last2=Zhu |first2=Daxin |last3=Tian |first3=Jun |title=2013 8th International Conference on Computer Science & Education |chapter=Efficient computation of matrix chain |date=April 2013 |pages=703–707 |doi=10.1109/ICCSE.2013.6553999|isbn=978-1-4673-4463-0 |s2cid=17303326 }}</ref>

Nimbark, Gohel, and Doshi have published a greedy ''O''(''n''&nbsp;log&nbsp;''n'') algorithm,<ref>{{cite book |last1=Nimbark |first1=Hitesh |last2=Gohel |first2=Shobhen |last3=Doshi |first3=Nishant |chapter=A Novel Approach for Matrix Chain Multiplication Using Greedy Technique for Packet Processing |title=Computer Networks and Information Technologies |series=Communications in Computer and Information Science |date=2011 |volume=142 |pages=318–321 |doi=10.1007/978-3-642-19542-6_58|isbn=978-3-642-19541-9 }}</ref> but their proof of optimality is incorrect and their algorithm fails to produce the most efficient parentheses assignment for some matrix chains.<ref name=Schwartz/>

=== Chin-Hu-Shing approximate solution ===
An algorithm created independently by Chin<ref>{{cite journal |last1=Chin |first1=Francis Y.|author1-link=Francis Y. L. Chin |title=An O(n) algorithm for determining a near-optimal computation order of matrix chain products |journal=Communications of the ACM |date=July 1978 |volume=21 |issue=7 |pages=544–549 |doi=10.1145/359545.359556|doi-access=free}}</ref> and Hu & Shing<ref>{{cite journal |last1=Hu |first1=T.C |last2=Shing |first2=M.T |title=An O(n) algorithm to find a near-optimum partition of a convex polygon |journal=Journal of Algorithms |date=June 1981 |volume=2 |issue=2 |pages=122–138 |doi=10.1016/0196-6774(81)90014-6}}</ref> runs in O(''n'') and produces a parenthesization which is at most 15.47% worse than the optimal choice. In most cases the algorithm yields the optimal solution or a solution which is only 1-2 percent worse than the optimal one.<ref name="Czumaj" />

The algorithm starts by translating the problem to the polygon partitioning problem. To each vertex ''V'' of the polygon is associated a weight ''w''. Suppose we have three consecutive vertices <math>V_{i-1}, V_i, V_{i+1}</math>, and that <math>V_{\min}</math> is the vertex with minimum weight <math>w_{\min}</math>.
We look at the quadrilateral with vertices <math>V_{\min}, V_{i-1}, V_i, V_{i+1}</math> (in clockwise order).
We can triangulate it in two ways:
*<math>(V_{\min}, V_{i-1}, V_i)</math> and <math>(V_{\min}, V_{i+1}, V_i)</math>, with cost <math>w_{\min}w_{i-1}w_i+w_{\min}w_{i+1}w_i</math>
*<math>(V_{\min}, V_{i-1}, V_{i+1})</math> and <math>(V_{i-1}, V_i, V_{i+1})</math> with cost <math>w_{\min}w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}</math>.

Therefore, if

: <math>w_{\min}w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}<w_{\min}w_{i-1}w_i+w_{\min}w_{i+1}w_i </math>

or equivalently

: <math>\frac{1}{w_i}+\frac{1}{w_{\min}}<\frac{1}{w_{i+1}}+\frac{1}{w_{i-1}} </math>

we remove the vertex <math>V_i</math> from the polygon and add the side <math>(V_{i-1}, V_{i+1})</math> to the triangulation.
We repeat this process until no <math>V_i</math> satisfies the condition above.
For all the remaining vertices <math>V_n</math>, we add the side <math>(V_{\min}, V_n)</math> to the triangulation. 
This gives us a nearly optimal triangulation.