Editing Matrix chain multiplication (section)

== Generalizations ==

The matrix chain multiplication problem generalizes to solving a more abstract problem: given a linear sequence of objects, an associative binary operation on those objects, and a way to compute the cost of performing that operation on any two given objects (as well as all partial results), compute the minimum cost way to group the objects to apply the operation over the sequence.<ref>G. Baumgartner, D. Bernholdt, D. Cociorva, R. Harrison, M. Nooijen, J. Ramanujam and P. Sadayappan. A Performance Optimization Framework for Compilation of Tensor Contraction Expressions into Parallel Programs. 7th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS '02). Fort Lauderdale, Florida. 2002 available at http://citeseer.ist.psu.edu/610463.html and at http://www.csc.lsu.edu/~gb/TCE/Publications/OptFramework-HIPS02.pdf</ref> A practical instance of this comes from the ordering of [[Join (SQL)|join]] operations in [[database]]s; see {{slink|Query optimization|Join ordering}}.

Another somewhat contrived special case of this is [[string concatenation]] of a list of strings. In [[C (programming language)|C]], for example, the cost of concatenating two strings of length ''m'' and ''n'' using ''strcat'' is O(''m''&nbsp;+&nbsp;''n''), since we need O(''m'') time to find the end of the first string and O(''n'') time to copy the second string onto the end of it. Using this cost function, we can write a dynamic programming algorithm to find the fastest way to concatenate a sequence of strings. However, this optimization is rather useless because we can straightforwardly concatenate the strings in time proportional to the sum of their lengths. A similar problem exists for singly [[linked lists]].

Another generalization is to solve the problem when parallel processors are available. In this case, instead of adding the costs of computing each factor of a matrix product, we take the maximum because we can do them simultaneously. This can drastically affect both the minimum cost and the final optimal grouping; more "balanced" groupings that keep all the processors busy are favored. There are even more sophisticated approaches.<ref>Heejo Lee, Jong Kim, Sungje Hong, and Sunggu Lee. [http://ccs.korea.ac.kr/pds/tpds03.pdf Processor Allocation and Task Scheduling of Matrix Chain Products on Parallel Systems] {{webarchive|url=https://web.archive.org/web/20110722132611/http://ccs.korea.ac.kr/pds/tpds03.pdf |date=2011-07-22 }}. ''IEEE Trans. on Parallel and Distributed Systems,'' Vol. 14, No. 4, pp.&nbsp;394–407, Apr. 2003</ref>