Editing Matrix multiplication (section)

====Computational complexity depends on parenthesization====
Although the result of a sequence of matrix products does not depend on the [[order of operation]] (provided that the order of the matrices is not changed), the [[computational complexity]] may depend dramatically on this order.

For example, if {{math|'''A''', '''B'''}} and {{math|'''C'''}} are matrices of respective sizes {{math|10×30, 30×5, 5×60}}, computing {{math|('''AB''')'''C'''}} needs {{math|1=10×30×5 + 10×5×60 = 4,500}} multiplications, while computing {{math|'''A'''('''BC''')}} needs {{math|1=30×5×60 + 10×30×60 = 27,000}} multiplications.

Algorithms have been designed for choosing the best order of products; see [[Matrix chain multiplication]]. When the number {{mvar|n}} of matrices increases, it has been shown that the choice of the best order has a complexity of <math>O(n \log n).</math><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>{{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>