Revision as of 12:26, 5 August 2023 (view source) PSNOW123 (talk \| contribs) (New post.) ← Older edit		Revision as of 22:40, 22 December 2023 (view source) Querfeld (talk \| contribs) mNo edit summary Newer edit →
Line 1: {{task\|Discrete math}} [[Category:Matrices]] ;Problem Using the most ~~straightfoward~~straightforward 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... 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. Line 30 ⟶ 31: =={{header\|11l}}== {{trans\|Nim}} <syntaxhighlight lang="11l">T Optimizer [Int] dims Line 477: =={{header\|Fortran}}== {{trans\|Python}} This is a translation of the Python iterative solution. Line 890 ⟶ 889: Cost : 1777600 </pre> =={{header\|Julia}}== Line 1,128 ⟶ 1,126: 1773740 1((((((23)4)(((56)7)8))9)10)11)</pre> =={{header\|MATLAB}}== {{trans\|Fortran}} <syntaxhighlight lang="matlab">function [r,s] = optim(a) n = length(a)-1; Line 1,573 ⟶ 1,569: =={{header\|R}}== <syntaxhighlight lang="rsplus">aux <- function(i, j, u) { k <- u[[i, j]] Line 1,627 ⟶ 1,622: =={{header\|Racket}}== '''Memoization'''

Matrix chain multiplication: Difference between revisions

Matrix chain multiplication (view source)

Revision as of 22:40, 22 December 2023