Enhanced Matrix Chain Multiplication
DOI:
https://doi.org/10.13052/2245-1439.743Keywords:
Matrix multiplication, Matrix Chain Multiplication, Dynamic Programming, Optimal ordering of matricesAbstract
Let A1, A2,....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(n3) 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(n3) if any two of the S values are not same and O(n3) when the two values of S are same in the worst case.
Downloads
References
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.
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.
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).
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.
Godbole, S. S. (1973). On efficient computation of matrix chain products. IEEE Transactions on Computers, 100(9):864–866.
Horowitz, E., Sahni, S. and Rajasekaran, S. (2006). Fundamentals of Computer Algorithms, 2nd Edition, Galgotia publications.
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to algorithms. Third Edition, MIT press.
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.
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.
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.
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.
