Matrix chain multiplication: Difference between revisions

Line 2:

;Problem

Using the most straightfoward algorithm (which we assume here), computing the [[Matrix multiplication|product of two matrices]] of dimensions (n1,n2) and (n2,n3) requires n1*n2*n3 [[wp:Multiply–accumulate_operation|FMA]] operations. The number of operations required to compute the product of matrices A1, A2... AN depends on the order of ~~operations~~, hence on where parens are put. Remember that the matrix product is associative, but not commutative, hence only the parens can be moved.

Using the most straightfoward algorithm (which we assume here), computing the [[Matrix multiplication|product of two matrices]] of dimensions (n1,n2) and (n2,n3) requires n1*n2*n3 [[wp:Multiply–accumulate_operation|FMA]] operations. The number of operations required to compute the product of matrices A1, A2... An depends on the order of matrix multiplications, hence on where parens are put. Remember that the matrix product is associative, but not commutative, hence only the parens can be moved.

For instance, with four matrices, one can compute A(B(CD)), A((BC)D), (AB)(CD), (A(BC))D, (AB)C)D. The number of different ways to put the parens is a [[Catalan numbers|Catalan number]], and grows exponentially with the number of factors.