Enhanced Matrix Chain Multiplication

B. Suvarna* and T. Maruthi Padmaja

Vignan’s Foundation for Science Technology and Research, AP, India

E-mail: sv1720@gmail.com; padmaja.tu2002@gmail.com

^∗Corresponding Author

Received 24 January 2018; Accepted 28 July 2018;
Publication 17 September 2018

Abstract

Let A₁, A₂,....An be the given sequence of n matrices, generally matrix chain multiplication algorithm is used to obtain its-product with minimum cost(lowest cost). However the matrix chain multiplication is a dynamic programming paradigm and takes O(n³) computational complexity. Here we present improved algorithm for matrix chain multiplication with minimum space and time complexities. The viability of this new algorithm is demonstrated using few examples and the performance is computationally verified. This algorithm does not take O(n³) if any two of the S values are not same and O(n³) when the two values of S are same in the worst case.

Keywords

Matrix multiplication
Matrix Chain Multiplication
Dynamic Programming
Optimal ordering of matrices

1 Introduction

Matrix Chain Multiplication is one of the optimization problem which is widely used in graph algorithms, signal processing and network industry [1–4]. We can have several ways to multiply the given number of matrices because the matrix multiplication is associative. In other words, there is no matter how the matrices are parenthesize to perform the product. Because the result will be the same. For example, if we had four matrices A₁, A₂, A₃, A₄ with dimensions A₁ = P₀ × P₁, A₂ = P₁ × P₂, A₃ = P₂ × P₃, A₄ = P₃ × P₄ then we would have the parenthesize of the above arrays, along with multiplication number are listed below.

Ex: A₁ = 2 × 3, A₂ = 3 × 4, A₃ = 4 × 5 and A₄ = 5 × 2

(A₁A₂)(A₃A₄) = P₀P₁P₂ + P₂P₃P₄ + P₀P₂P₄ = 80 multiplications

((A₁A₂)A₃)A₄ = P₀P₁P₂ + P₀P₂P₃ + P₀P₃P₄ = 84 multiplications

(A₁(A₂A₃))A₄ = P₀P₁P₃ + P₁P₂P₃ + P₀P₃P₄ = 110 multiplications

A₁((A₂A₃)A₄) = P₁P₂P₃ + P₁P₃P₄ + P₀P₁P₄ = 102 multiplications

A₁(A₂(A₃A₄)) = P₁P₂P₃ + P₁P₃P₄ + P₀P₁P₄ = 76 multiplications

From the above observation, we can say that the last one is taking minimum number of multiplications. But comparison of each and every possible parenthesize like brute force approach would take exponential time depending on the number of matrices. This process is not suitable to implement where there is more number of matrices to multiply. A fastest possible solution to this matrix chain multiplication can be achieved by dividing the problem into a set of sub problems. By this the time complexity will be reduced by solving sub problems once and reusing the solutions as in the design technique of dynamic programming [5].

Example

Let n = 4, where n is the number of matrices has different dimensions P_i-1 × P_i

A₁ = 3 × 4 A₂ = 4 × 6 A₃ = 6 × 7 A₄ = 7 × 2 then find the sequences of matrices to multiply

P(0:n)=(3,4,6,7,2) is the single dimensional matrix

The values of M and S for the first row are calculated by using the Equations (1) and (2). The remaining values of M and S can be calculated by using the following logic.

images

Table 1 Calculation of M and S values for the given example

M₁₁=0	M₂₂=0	M₃₃=0	M₄₄=0
S₁₁=0	S₂₂=0	S₃₃=0	S₄₄=0
M₁₂=72	M₂₃=168	M₃₄=84
S₁₂=1	S₂₃=2	S₃₄=3
M₁₃=198	M₂₄=132
S₁₃=2	S₂₄=2
M₁₄=156
S₁₄=2

Where M[x, y] is the minimum number of multiplications required by each pair and S[x, y] be the value of contains the minimum z which is used for where to place parenthesis to split the product A_x, A_x+1,.... A_y for 1≤x≤y≤n.

The above example shows how the equation can be used to determine M’s and S’s. Now let us examine the time requirement of the above procedure to construct M’s and S’s to calculate M(x,y) for y-x = 1,2,…n in that order when y-x = w there are n-w+1 M(x,y)’s to compute. The total time for all M(x,y) with y-x = m is therefore O(nm-m²). And the total time to compute M(x,y) and S(x,y) is $\sum_{1 \leq m \leq n} (n w - w^{2}) = O (n^{3})$ [6].

However we can do better than this for finding optimal z (used for parenthesize) by limiting search from the range of S(x,y-1) to S(x+1,y) proposed by D.E Knuth instead of repeating the z from x to y-1 which is nearly equal to n.

2 Existing Algorithm

Existing algorithm for matrix chain multiplication is presenting here.

images

In the existing algorithm given for finding a sequence and finding the less number of multiplications takes O(n³) because the algorithm is composed with 3 loops and each loop takes at most n-1 times [7]. For that we proposed an algorithm for finding the sequence of matrices to multiply with the less time.

3 Proposed Algorithm

Time complexity is reduced by limiting the search for z from S(x, y-1) to S(x+1,y). However the formulas for computing the rows of the table are described below.

The values for M’s and S’s of first row can be computed by the formula

Set M[x, x] to 0, where x is from 1 to n (1)

Set S[x, x] to 0, where x is from 1 to n (2)

And for to compute the values for M’s and S’s of second row, the formulas are given below.

M[x][x+1]=M[x][x]+M[x+1][x+1]+P[x-1]*p[x]*p[x+1] where y-x=1,2,…n (3)

S[x][x+1]=x; where y-x = 1,2,…n

And for to compute the remaining rows below formula can be used

M[x, y]= M[x, z]+M[z+1,y]+P[x-1]*P[z]*P[y];

S[x, y]=z;

Following are the complete algorithms for finding the M’s and S values

images

From the above algorithm the find_ of_ z function is used to calculate the minimum value for z, The z value is getting by repeating the loop from S[x,y-1] to S[x+1,y] instead of repeating the z from x to y-1 which is taking at most n-1 times.

Hence the above find_ of_ z function is again modified “if S[x,y-1] is less than S[x+1,y] then the z will repeat S[x,y-1] to S[x+1,y] else it will repeat from x to y-1.

This type of z which repeats from x to y-1 may or may not be occurred for all the type of inputs. This can be observed in Tables 2 and 3.

4 Results

This section demonstrates the proposed approach by considering example. The above proposed algorithm is implemented and tested for the following input. The experimental result values of M and S are given in the form of table.

Example 1: n=5,(P₀,P₁,P₂,P₃,P_4,P₅)=(3,4,6,2,3,7)

Table 2 Results for M values

M values
0	0	0	0	0
72	48	36	42
72	72	126
90	146
153

Table 3 Results for S values

S values
0	0	0	0	0
1	2	3	4
1	3	3
3	3
2

Output sequence is (((A1(A2A3))A4)A5)

Example 2: n=4,(P₀,P₁,P₂,P₃,P₄)=(3,4,6,7,2)

Table 4 Results for M values

M values
0	0	0	0
72	168	84
198	132
156

Table 5 Results for S values

S values
0	0	0	0
1	2	3
2	2
2

Output sequence is (A1(A2(A3A4)))

Example 3: n=4,(P₀,P₁,P₂,P₃,P₄)=(2,3,6,4,5)

Table 6 Results for M values

M values
0	0	0	0
36	72	120
84	132
124

Table 7 Results for S values

S values
0	0	0	0
1	2	3
2	3
2

Sequence is (((A1A2) A3) A4)

From the above Table 3 the values of S₁₄ and S₂₅ and also S_13, S₂₄ in the Table 4 which are marked as red have same cut so at this case only it is running three nested loops; otherwise it does not run three nested loops. However the corresponding S values are marked with red color (in the tables) at which the algorithm is running three nested loops. Otherwise it will not run three nested loops. From this observation we can claim that this Matrix_Chain_Multiplication algorithm will not take O(n³) time.

By observing the above tables we can say that the algorithm for finding minimum split i.e. z will take only from S[x, y-1] and S[x+1, y] instead of repeating for n-1 times.

This algorithm does not take O(n³) if any two of the S values are not same and O(n³) when the two values of S are same in the worst case.

5 Conclusion

From the above discussion we can say that the proposed matrix chain multiplication algorithm using Dynamic Programming in the best case and average case takes O(n²) time complexity which is less when it is compared with existing matrix chain multiplication which takes O(n³). Hence the time complexity is reduced with the space requirement of O(n²).

References

[1] Shyamala, K., Raj Kiran, K., and Rajeshwari, D. (2017). Design and implementation of GPU-based matrix chain multiplication using C++ AMP. In 2017 Second International Conference on Electrical, Computer and Communication Technologies (ICECCT), (pp. 1–6). IEEE.

[2] Mabrouk, B. B., Hasni, H. and Mahjoub, Z. (2014). Performance evaluation of a parallel dynamic programming algorithm for solving the matrix chain product problem. In 2014 IEEE/ACS 11th International Conference on Computer Systems and Applications (AICCSA), (pp. 109–116). IEEE.

[3] Cáceres, E. N., Mongelli, H., Loureiro, L., Nishibe, C. and Song, S.W. (2009). A parallel chain matrix product algorithm on the InteGrade grid. In International Conference on High Performance Computing, Grid and e-Science in Asia Pacific Region (pp. 304–311).

[4] Lakhotia, R., Kumar, S., Sood, R., Singh, H. and Nabi, J. (2015). Matrix-Chain Multiplication Using Greedy and Divide-Conquer approach. International Journal of Computer Trends and Technology (IJCTT), 23(2):65–72. Doi: 10.14445/22312803/IJCTT-V23P115.

[5] Godbole, S. S. (1973). On efficient computation of matrix chain products. IEEE Transactions on Computers, 100(9):864–866.

[6] Horowitz, E., Sahni, S. and Rajasekaran, S. (2006). Fundamentals of Computer Algorithms, 2nd Edition, Galgotia publications.

[7] Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to algorithms. Third Edition, MIT press.

[8] Nishida, K., Ito, Y. and Nakano, K. (2011). Accelerating the dynamic programming for the matrix chain product on the GPU. In 2011 Second International Conference on Networking and Computing (pp. 320–326). IEEE.

[9] Parvaresh, F. and Vardy, A. (2004). Polynomial matrix-chain interpolation in Sudan-type Reed-Solomon decoders. International Symposium on Information Theory, 2004. ISIT 2004. IEEE. Proceedings. Doi: 10.1109/ISIT.2004.1365424.

[10] Lee, H., Kim, J., Hong, S. J. and Lee, S. (2003). Processor allocation and task scheduling of matrix chain products on parallel systems. IEEE Transactions on Parallel & Distributed Systems, (4):394–407.

[11] Myung, J. and Lee, S. G. (2012). Matrix chain multiplication via multi-way join algorithms in MapReduce. In Proceedings of the 6th International Conference on Ubiquitous Information Management and Communication (p. 53). ACM.

Biographies

images

B. Suvarna is pursuing Ph.D in VFSTR deemed to be University. Prior to that she has received M.Tech degree from vignan’s Engineering college affiliated to JNTU Kakinada and B.Tech degree from VR Siddhartha Engineering college affiliated to ANU. Currently she is working as an Asst Professor, CSE Department, VFSTR deemed to be University, AP, INDIA. Her research interests include Data Mining, Machine Learning and analysis of algorithms.

images

T. Maruthi Padmaja, received Ph.D degree from the University of Hyderabad, Hyderabad. During that time she was a research scholar at IDRBT, Hyderabad. Prior to that she has received M.Tech degree from the Tezpur University, Assam. Currently, she is working as an Associate Professor, CSE Department, VFSTR University, AP. Her research interests include Data Mining, Machine Learning and Pattern Recognition.