Matrix chain multiplication

Matrix chain multiplication refers to the multiplication of several matrices . Since the matrix multiplication is associative , you can use brackets as you wish. As a result, the number of possible calculation paths increases polynomially with the length of the matrix chain. With the method of dynamic programming , the bracketing of the matrix chain can be optimized so that the total number of arithmetic operations is minimized. The algorithm has a running time of . ${\ displaystyle O}$ ${\ displaystyle (n ^ {3})}$

The number of possible brackets for matrices can be determined with the Catalan number C _n-1 . ${\ displaystyle n}$

Example: Let be a 10 × 30 matrix, a 30 × 5 matrix and a 5 × 60 matrix. Then there are two different ways to clamp the die product: ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle C}$ ${\ displaystyle ABC}$

{\ displaystyle (AB) C}

{\ displaystyle A (BC)}

The number of basic operations is calculated as follows:

{\ displaystyle (AB) C \ rightarrow (10 \ cdot 30 \ cdot 5) + (10 \ cdot 5 \ cdot 60) = 1500 + 3000 = 4500}

{\ displaystyle A (BC) \ rightarrow (30 \ cdot 5 \ cdot 60) + (10 \ cdot 30 \ cdot 60) = 9000 + 18000 = 27000}

algorithm

The algorithm calculates a result matrix using dynamic programming. In the case of a chain of matrices, the input of the algorithm is the sequence of the dimension pairs, whereby the function firstdim or seconddim applied to a matrix or returns. ${\ displaystyle A_ {0} A_ {1} A_ {2} \ ldots A_ {n-1}}$ ${\ displaystyle n}$ ${\ displaystyle s}$ ${\ displaystyle s = [({\ mathit {firstdim}} (A_ {i}), {\ mathit {seconddim}} (A_ {i})) | 0 \ leq i <n]}$ ${\ displaystyle m \ times n}$ ${\ displaystyle m}$ ${\ displaystyle n}$

${\ displaystyle s [0..2]}$ denotes the partial sequence of s that contains the first two pairs of dimensions. So is . ${\ displaystyle s [0 .. {\ mathit {length}} (s)] = s}$

The algorithm is specified by a matrix recurrence.

initialization

${\ displaystyle M [i, i + 2] = {\ mathit {firstdim}} (i) \ cdot {\ mathit {seconddim}} (i + 1) \ cdot {\ mathit {firstdim}} (i + 1) , ~ 0 \ leq i <{\ mathit {length}} (s) -1}$

For every two matrices long chains there is only one possibility of bracketing.

Recursion

${\ displaystyle M [i, j] = \ min _ {i <k <j} {\ big \ {} M [i, k] + M [k + 1, j] + {\ mathit {firstdim}} ( i) \ cdot {\ mathit {seconddim}} (j-1) \ cdot {\ mathit {firstdim}} (k) {\ big \}}}$ ,

whereby . ${\ displaystyle i + 2 <j, 0 \ leq i \ leq {\ mathit {length}} (s), 0 \ leq j \ leq {\ mathit {length}} (s)}$

The cell contains the minimum number of basic arithmetic operations to multiply the partial sequence of the matrix chain. So the minimum number of operations when multiplying the entire chain is stored in the cell . ${\ displaystyle M [i, j]}$ ${\ displaystyle s [i..j]}$ ${\ displaystyle M [0, {\ mathit {length}} (s)]}$

To construct the optimal stapling, to the optimal result has led must in the path of the DP matrix by backtracking from be from traced. ${\ displaystyle M [0, {\ mathit {length}} (s)]}$ ${\ displaystyle M}$ ${\ displaystyle M [0, {\ mathit {length}} (s)]}$

Efficiency

The length of the input sequence is denoted by. The algorithm needs a square matrix to store the intermediate results for all partial sequences . So the memory requirement is in . ${\ displaystyle n}$ ${\ displaystyle n \ times n}$ ${\ displaystyle O (n ^ {2})}$

Each cell has to be optimized via divisions. So the total runtime is in ${\ displaystyle O (n)}$ ${\ displaystyle O (n ^ {3})}$

variants

The optimization algorithm can be used for any sequences of objects which are chained by an associative operation if a cost function exists for the execution of the operation.

The number of brackets in can be calculated by simply modifying the recurrence . ${\ displaystyle O (n ^ {3})}$

Demarcation

Cormen, 2001 (p. 369), refers to an algorithm by Hu and Shing for the optimization of brackets in matrix chain multiplication, which has a running time of . ${\ displaystyle O (n \ log n)}$

literature

Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Introduction to Algorithms . 2nd Edition. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7 , pp. 331-338 .
TC Hu, MT Shing: Computation of Matrix Chain Products. Part I . In: SIAM Journal on Computing . tape 11 , no. 2 , 1982, p. 362-373 , doi : 10.1137 / 0211028 .

swell

↑ Hu Shing, Computation of Matrix Chain Products, Part I, Part II. 1980, Report.

[1] Hu Shing, Computation of Matrix Chain Products, Part I, Part II. 1980, Report.