Editing Matrix chain multiplication (section)

{{Short description|Mathematics optimization problem}}
'''Matrix chain multiplication''' (or the '''matrix chain ordering problem'''<ref name=Schwartz/>) is an [[optimization problem]] concerning the most efficient way to [[matrix multiplication|multiply]] a given sequence of [[Matrix (mathematics)|matrices]].  The problem is not actually to ''perform'' the multiplications, but merely to decide the sequence of the matrix multiplications involved.  The problem may be solved using [[dynamic programming]].

There are many options because matrix multiplication is [[associativity|associative]]. In other words, no matter how the product is [[Bracket (mathematics)|parenthesize]]d, the result obtained will remain the same. For example, for four matrices ''A'', ''B'', ''C'', and ''D'', there are five possible options:

:((''AB'')''C'')''D'' = (''A''(''BC''))''D'' = (''AB'')(''CD'') = ''A''((''BC'')''D'') = ''A''(''B''(''CD'')).

Although it does not affect the product, the order in which the terms are parenthesized affects the number of simple arithmetic operations needed to compute the product, that is, the [[computational complexity]]. The straightforward multiplication of a matrix that is {{math|''X'' × ''Y''}} by a matrix that is {{math|''Y'' × ''Z''}} requires {{math|''XYZ''}} ordinary multiplications and {{math|''X''(''Y'' − 1)''Z''}} ordinary additions.  In this context, it is typical to use the number of ordinary multiplications as a measure of the runtime complexity.

If ''A'' is a 10 × 30 matrix, ''B'' is a 30 × 5 matrix, and ''C'' is a 5 × 60 matrix, then

:computing (''AB'')''C'' needs (10×30×5) + (10×5×60)  = 1500 + 3000 = 4500 operations, while
:computing ''A''(''BC'') needs (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

Clearly the first method is more efficient. With this information, the problem statement can be refined as "how to determine the optimal parenthesization of a product of ''n'' matrices?" The number of possible parenthesizations is given by the (''n''–1)<sup>th</sup> [[Catalan  number]], which is [[Big O notation|''O'']](4<sup>''n''</sup> / ''n''<sup>3/2</sup>), so checking each possible parenthesization ([[Brute-force search|brute force]]) would require a [[Time complexity|run-time]] that is exponential in the number of matrices, which is very slow and impractical for large ''n''. A quicker solution to this problem can be achieved by breaking up the problem into a set of related subproblems.