Matrix chain multiplication

Matrix - chain multiplication denotes the multiplication of several matrices. Since matrix multiplication is associative, we can cling arbitrarily. Characterized the number of possible calculation paths grows exponentially with the length of the Matrizenkette. With the method of dynamic programming, the compounding of the matrix - chain can be optimized so that the total number of arithmetic operations is minimized. The algorithm has a running time of.

The number of parantheses for matrices can be determined with the Catalan number Cn -1.

Example: Let be a 10 × 30 matrix, a 30 × 5 matrix and a 5 × 60 matrix. Then there are two different ways to clinch the matrix product:

The number of basic operations is calculated as follows:

Algorithm

The algorithm calculates by means of dynamic programming, a score matrix. In a chain of matrices, the input of the algorithm is the sequence of dimension pairs, where the firstdim function or seconddim applied to a matrix or returns.

Refers to the partial sequence of S, that contains the first two pairs of dimensions. So is.

The algorithm is specified by a matrix recurrence.

For any two matrices long chains there is only one way of bracketing.

,

Said.

In the cell is the minimum number of basic arithmetic operations for multiplying the partial sequence of Matrizenkette. Thus, the minimum number of operations is stored in the multiplication of the entire chain in the cell.

To construct the optimal bracketing, which has led to the optimal result, the path must be traced in the DP matrix by means of backtracking from.

Efficiency

The length of the input sequence is denoted by. The algorithm needed to store the intermediate results for all sub- sequences a square matrix. So the storage requirement is.

For each cell must be optimized over partitions. So the total running time is in

Variants

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

By a simple modification of the number of recurrences may be calculated in parantheses.

Demarcation

Cormen, 2001 ( p. 369 ), refers to an algorithm of Hu and Shing to optimize use of parentheses in the matrix - chain multiplication, which has a term of.