Chain Matrix Multiplication

Chain Matrix Multiplication

Matrix-chain Multiplication  Problem

 

The chain matrix multiplication problem is perhaps the most popular example of dynamic programming used in the upper undergraduate course (or review basic issues of dynamic programming in advanced algorithm's class).

The chain matrix multiplication problem involves the question of determining the optimal sequence for performing a series of operations. This general class of problem is important in complier design for code optimization and in databases for query optimization. We will study the problem in a very restricted instance, where the dynamic programming issues are clear. Suppose that our problem is to multiply a chain of n matrices A₁ A₂ ... A_n. Recall (from your discrete structures course), matrix multiplication is an associative but not a commutative operation. This means that you are free to parenthesize the above multiplication however we like, but we are not free to rearrange the order of the matrices. Also, recall that when two (non-square) matrices are being multiplied, there are restrictions on the dimensions.

Suppose, matrix A has p rows and q columns i.e., the dimension of matrix A is p × q. You can multiply a matrix A of p × q dimensions times a matrix B of dimensions q × r, and the result will be a matrix C with dimensions p × r. That is, you can multiply two matrices if they are compatible: the number of columns of A must equal the number of rows of B.

In particular, for 1 ≤ i ≤  p and 1 ≤ j ≤ r, we have

C[i, j] = ∑_{1 ≤ k ≤ q} A[i, k] B[k, j].

There are p . r total entries in C and each takes O(q) time to compute, thus the total time to multiply these two matrices is dominated by the number of scalar multiplication, which is p . q . r.

 

Problem Formulation

Note that although we can use any legal parenthesization, which will lead to a valid result. But, not all parenthesizations involve the same number of operations. To understand this point, consider the problem of a chain A₁, A₂, A₃ of three matrices and suppose

A₁ be of dimension 10 × 100
A₂ be of dimension 100 × 5
A₃ be of dimension 5 × 50

Then,

MultCost[((A₁ A₂) A₃)] = (10 . 100 . 5) +  (10 . 5 . 50) = 7,500 scalar multiplications.

MultCost[(A₁ (A₂ A₃))] = (100 . 5 . 50) + (10 . 100 . 50) = 75,000 scalar multiplications.

It is easy to see that even for this small example, computing the product according to first parenthesization is 10 times faster.

Read full article from Chain Matrix Multiplication