Revision as of 12:03, 12 April 2018 (view source) Eoraptor (talk \| contribs) m (→‎Memoized recursive call) ← Older edit		Revision as of 12:21, 12 April 2018 (view source) Eoraptor (talk \| contribs) mNo edit summary Newer edit →
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 n1n2n3 [[wp:Multiply–accumulate_operation\|FMA]] operations. The number of operations required to compute the product of matrices A1, A2... ANAn depends on the order of ~~operations~~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.

Matrix chain multiplication: Difference between revisions

Matrix chain multiplication (view source)