## 3.4 Chained Matrix Multiplication Suppose we want to multiply a 2 × 2 matrix times a 3 × 4 matrix as follows:  The resultant matrix is a 2 × 2 matrix. If we use the standard method of multiplying matrices (that is, the one obtained from the definition of matrix multiplication), it takes three elementary multiplications to compute each item in the product. For example, the first time in the first column is given by  Because there are 2 × 4 = 8 entries in the product, the total number of elementary multiplication is  In general, to multiply an *i* × *j* matrix times a *j* × *k* matrix using the standard method, it is necessary to do  Consider the multiplication of the following four matrices:  The dimension of each matrix appears under the matrix. Matrix multiplication is an associative operation, meaning that the order in which we multiply does not matter. For example, *A* (*B* (*CD*)) and (*AB* (*CD*) both give the same answer. There are five different orders in which we can multiply four matrices, each possibly resulting in a different number of elementary multiplications. In the case of the previous matrices, we have the following number of elementary for each order.  The third order is the optimal order for multiplying the four matrices. Our goal is to develop an algorithm that determines the optimal order for multiplying *n* matrices. The optimal order depends only on the dimensions of the matrices. Therefore, besides *n*, these dimensions would be the only input to the algorithm. The brute-force algorithm is to consider all possible orders and take the minimum, as we just did. We will show that this algorithm is at least exponential-time. To this end, let *t*n be the number of different orders in which we can multiply *n* matrices: *A*1, *A*2, …, *A**n*. A subset of all the orders is the set of orders for which *A*1 is the last matrix multiplied. As illustrated below, the number of different in this subset is *t**n*-1, because it is the number of different orders with which we can multiply *A*2 through *A**n*:  A second subset of all the orders is the set of orders for which *A**n* is the last matrix multiplied. Clearly, the number of different orders in this subset is also *t**n*−1. Therefore,  Because there is only one way to multiply two matrices, *t*2 = 1. Using the techniques in [Appendix B](LiB0102.html#1369), we can solve this recurrence to show that  It is not hard to see that the principle of optimality applies in this problem. That is, the optimal order for multiplying *n* matrices includes the optimal order for multiplying any subset of the *n* matrices. For example, if the optimal order for multiplying six particular matrices is  then  must be the optimal order for multiplying matrices *A*2 through *A*4. This means we can use dynamic programming to construct a solution. Because we are multiplying the (*k* − 1)st matrix, *A**k*−1, times the *k*th matrix, *A**k*, the number of columns in *A**k*−1 must equal the number of rows in *A**k*. For example, in the product discussed earlier, the first matrix has three columns and the second has three rows. If we let *d*0 be the number of rows in *A*1 and *d**k* be the number of columns in *A**k* for 1 ≤ *k* ≤ *n*, the dimension of *A*k is *d*k−1 x *d*k. This is illustrated in [Figure 3.7](#ch03fig07). [](fig3-7_0.jpg) Figure 3.7: The number of columns in *A*k−1 is the same as the number of rows in *A*k As in the previous section, we will use a sequence of arrays to construct our solution. For 1 ≤ *i* ≤ *j* ≤ *n*, let *M* \[*i*\] \[*j*\] = minimum number of multiplications needed to multiply *Ai* through  Before discussing how we will use these arrays, let's illustrate the meanings of the items in them. Example 3.5****Suppose we have the following six matrices:  To multiply *A*4, *A*5, and *A*6, we have the following two orders and numbers of elementary multiplications:  Therefore,  **** The optimal order for multiplying six matrices must have one of these factorizations: 1. *A*1 (*A*2*A*3*A*4*A*5*A*6) 2. (*A*1*A*2) (*A*3*A*4*A*5*A*6) 3. (*A*1*A*2*A*3) (*A*4*A*5*A*6) 4. (*A*1*A*2*A*3*A*4) (*A*5*A*6) 5. (*A*1*A*2*A*3*A*4*A*5) (*A*6) where inside each parentheses the products are obtained according to the optimal order for the matrices inside the parentheses. Of these factorizations, the one that yields the minimum number of multiplications must be the optimal one. The number of multiplications for the *k*th factorization is the minimum number needed to obtain each factor plus the number needed to multiply the two factors. This means that it equals  We have established that  There is nothing in the preceding argument that restricts the first matrix to being *A*1 or the last matrix to being *A*6. For example, we could have obtained a similar result for multiplying *A*2 through *A*6. Therefore, we can generalize this result to obtain the following recursive property when multiplying *n* matrices. For 1 ≤ *i* ≤ *j* ≤ *n*  A divide-and-conquer algorithm based on this property is exponential-time. We develop a more efficient algorithm using dynamic programming to compute the values of *M* \[*i*\] \[*j*\] in steps. A grid similar to Pascal's triangle is used (see [Section 3.1](LiB0025.html#256)). The calculations, which are a little more complex than those in [Section 3.1](LiB0025.html#256), are based on the following property of Equality 3.5: *M* \[*i*\] \[*j*\] is calculated from all entries on the same row as *M* \[*i*\] \[*j*\] but to the left of it along with all entries in the same column as *M* \[*i*\] \[*j*\] but beneath it. Using this property, we can compute the entries in *M* as follows: First we set all those entries in the main diagonal to 0; next we compute all those entries in the diagonal just above it, which we call diagonal 1; next we compute all those entries in diagonal 2; and so on. We continue in this manner until we compute the only entry in diagonal 5, which is our final answer, *M* \[1\] \[6\]. This procedure is illustrated in [Figure 3.8](#ch03fig08) for the matrices in [Example 3.5](#ch03ex10). The following example shows the calculations. [](fig3-8_0.jpg) Figure 3.8: The array *M* developed in [Example 3.5](#ch03ex10). *M* \[1\] \[4\], which is circled, is computed from the pairs of entries indicated Example 3.6****Suppose we have the six matrices in [Example 3.5](#ch03ex10). The steps in the dynamic programming algorithm follow. The results appear in [Figure 3.8](#ch03fig08).  Compute diagonal 1:  The values of *M* \[2\] \[3\], *M* \[3\] \[4\], *M* \[4\] \[5\], and *M* \[5\] \[6\] are computed in the same way. They appear in [Figure 3.8](#ch03fig08). Compute diagonal 2:  The values of *M* \[2\] \[4\], *M* \[3\] \[5\], and *M* \[4\] \[6\] are computed in the same way and are shown in [Figure 3.8](#ch03fig08). Compute diagonal 3:  The values of *M* \[2\] \[5\] and *M* \[3\] \[6\] are computed in the same manner and are shown in [Figure 3.8](#ch03fig08). Compute diagonal 4: The entries in diagonal 4 are computed in the same manner and are shown in [Figure 3.8](#ch03fig08). Compute diagonal 5: Finally, the entry in diagonal 5 is computed in the same manner. This entry is the solution to our instance; it is the minimum number of elementary multiplications, and its value is given by  **** The algorithm that follows implements this method. The dimensions of the *n* matrices—namely, the values of *d*0 through *dn*—are the only inputs to the algorithm. Matrices themselves are not inputs because the values in the matrices are irrelevant to the problem. The array *P* produced by the algorithm can be used to print the optimal order. We discuss this after analyzing [Algorithm 3.6](#ch03ex12). Algorithm 3.6: Minimum Multiplications****Problem: Determining the minimum number of elementary multiplications needed to multiply *n* matrices and an order that produces that minimum number. Inputs: the number of matrices *n*, and an array of integers *d*, indexed from 0 to *n*, where *d* \[*i* − 1\] x *d* \[*i*\] is the dimension of the *i*th matrix. Outputs: *minmult*, the minimum number of elementary multiplications needed to multiply the *n* matrices; a two-dimensional array *P* from which the optimal order can be obtained. *P* has its rows indexed from 1 to *n* − 1 and its columns indexed from 1 to *n.* *P* \[*i*\] \[*j*\] is the point where matrices *i* through *j* are split in an optimal order for multiplying the matrices. ``` int minmult (int n, const int d [], index P [] [] ) { index i, j, k, diagonal; int M [1 .. n] [1 .. n]; for (i = 1; i < = n; i++) M[i] [i] = 0; for (diagonal = 1; diagonal < = n - 1; diagonal ++) // Diagonal-1 is for (i = 1; i <= n - diagonal; i++) { // just above the j = i + diagonal; // main diagonal M[i] [j] = minimum (M[i] [k] + M[k + 1] [j] + d[i - 1]* d[k] * d[j]); i ≤ k ≤ j - 1 P[i] [j] = a value of k that gave the minimum; } return M[1] [n]; } ``` **** Next we analyze [Algorithm 3.6](#ch03ex12). ****Analysis of Algorithm 3.6 Every-Case Time Complexity (Minimum Multiplications)Basic operation: We can consider the instructions executed for each value of *k* to be the basic operation. Included is a comparison to test for the minimum. Input size: *n*, the number of matrices to be multiplied. We have a loop within a loop within a loop. Because *j* = *i* + *diagonal*, for given values of *diagonal* and *i*, the number of passes through the *k* loop is  For a given value of *diagonal*, the number of passes through the **for**-*i* loop is *n* − *diagonal.* Because *diagonal* goes from 1 to *n* − 1, the total number of times the basic operation is done equals  In the exercises we establish that this expression equals  **** Next we show how an optimal order can be obtained from the array *P*. The values of that array, when the algorithm is applied to the dimensions in [Example 3.5](#ch03ex10), are shown in [Figure 3.9](#ch03fig09). The fact that, for example, *P* \[2\] \[5\] = 4 means that the optimal order for multiplying matrices *A*2 through *A*5 has the factorization  [](fig3-9_0.jpg) Figure 3.9: The array *P* produced when [Algorithm 3.6](#ch03ex12) is applied to the dimensions in [Example 3.5](#ch03ex10). where inside the parentheses the matrices are multiplied according to the optimal order. That is, *P* \[2\] \[5\], which is 4, is the point where the matrices should be split to obtain the factors. We can produce an optimal order by visiting *P* \[1\] \[*n*\] first to determine the top-level factorization. Because *n* = 6 and *P* \[1, 6\] = 1, the top-level factorization in the optimal order is  Next we determine the factorization in the optimal order for multiplying *A*2 through *A*6 by visiting *P* \[2\] \[6\]. Because the value of *P* \[2\] \[6\] is 5, that factorization is  We now know that the factorization in the optimal order is  where the factorization for multiplying *A*2 through *A*5 must still be determined. Next we look up *P* \[2\] \[5\] and continue in this manner until all the factorizations are determined. The answer is  The following algorithm implements the method just described. Algorithm 3.7: Print Optimal Order****Problem: Print the optimal order for multiplying *n* matrices. Inputs: Positive integer *n*, and the array *P* produced by [Algorithm 3.6](#ch03ex12). *P* \[*i*\] \[*j*\] is the point where matrices *i* through *j* are split in an optimal order for multiplying those matrices. Outputs: the optimal order for multiplying the matrices. ``` void order (index i, index j) { if (i == j) cout << "A" << i; else { k = P[i] [j]; cout << "("; order (i, k); order (k + 1, j); cout << ")"; } } ``` **** Following our usual convention for recursive routines, *P* and *n* are not inputs to *order*, but are inputs to the algorithm. If the algorithm were implemented by defining *P* and *n* globally, the top-level call to *order* would be as follows: ``` order (1, n); ``` When the dimensions are those in [Example 3.5](#ch03ex10), the algorithm prints the following:  There are parentheses around the entire expression because the algorithm puts parentheses around every compound term. In the exercises we establish for [Algorithm 3.7](#ch03ex13) that  Our Θ (*n*3) algorithm for chained matrix multiplication is from Godbole (1973). Yao (1982) developed methods for speeding up certain dynamic programming solutions. Using those methods, it is possible to create a Θ (*n*2) algorithm for chained matrix multiplication. Hu and Shing (1982, 1984) describe a Θ (*n* lg *n*) algorithm for chained matrix multiplication.