Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Matrix chain multiplication
open-in-new
<p>Matrix chain multiplication (or the matrix chain ordering problem) is an <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a> concerning the most efficient way to <a href="/facts/Matrix_multiplication/lYDB6Ro2">multiply</a> a given sequence of <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrices</a>. The problem is not actually to <i>perform</i> the multiplications, but merely to decide the sequence of the matrix multiplications involved. The problem may be solved using <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a>. </p><p>There are many options because matrix multiplication is <a href="/facts/Associativity/EQX8lV6r">associative</a>. In other words, no matter how the product is <a href="/facts/Bracket_(mathematics)/yFLQxS0q">parenthesized</a>, the result obtained will remain the same. For example, for four matrices <i>A</i>, <i>B</i>, <i>C</i>, and <i>D</i>, there are five possible options: </p> ((<i>AB</i>)<i>C</i>)<i>D</i> = (<i>A</i>(<i>BC</i>))<i>D</i> = (<i>AB</i>)(<i>CD</i>) = <i>A</i>((<i>BC</i>)<i>D</i>) = <i>A</i>(<i>B</i>(<i>CD</i>)). <p>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 <a href="/facts/Computational_complexity/Qenh22Ja">computational complexity</a>. The straightforward multiplication of a matrix that is <i>X</i> × <i>Y</i> by a matrix that is <i>Y</i> × <i>Z</i> requires <i>XYZ</i> ordinary multiplications and <i>X</i>(<i>Y</i> − 1)<i>Z</i> ordinary additions. In this context, it is typical to use the number of ordinary multiplications as a measure of the runtime complexity. </p><p>If <i>A</i> is a 10 × 30 matrix, <i>B</i> is a 30 × 5 matrix, and <i>C</i> is a 5 × 60 matrix, then </p> computing (<i>AB</i>)<i>C</i> needs (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations, while computing <i>A</i>(<i>BC</i>) needs (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations. <p>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 <i>n</i> matrices?" The number of possible parenthesizations is given by the (<i>n</i>–1)th <a href="/facts/Catalan_number/R9vd4D3V">Catalan number</a>, which is <a href="/facts/Big_O_notation/weFFjSWg"><i>O</i></a>(4<i>n</i> / <i>n</i>3/2), so checking each possible parenthesization (<a href="/facts/Brute-force_search/YU2fzBIt">brute force</a>) would require a <a href="/facts/Time_complexity/77T62gmf">run-time</a> that is exponential in the number of matrices, which is very slow and impractical for large <i>n</i>. A quicker solution to this problem can be achieved by breaking up the problem into a set of related subproblems. </p>