| Paper title: |
Simplified Optimal Parenthesization Scheme for Matrix Chain Multiplication Problem using Bottom-up Practice in 2-Tree Structure |
| Published in: | Issue 2, (Vol. 5) / 2011 |
| Publishing date: | 2011-10-28 |
| Pages: | 9-14 |
| Author(s): | BHOWMIK Biswajit |
| Abstract. | Dynamic Programming is one of the sledgehammers of the algorithms craft in optimizations. The versatility of the dynamic programming method is really appreciated by exposure to a wide variety of applications. In this paper a modified algorithm is introduced to provide suitable procedure that ensures how to multiply a chain of matrices. The model Optimal Parenthesization Scheme using 2-Tree Generation (OPS2TG) acts as one relevancies of the proposed algorithm. A new approach for how to break the matrix chain and how to insert parenthesis in it is also designed in this model. The comparison study between the proposed model and the classical approach shows acceptance of the model suggested her |
| Keywords: | Scalar Multiplication, Optimal Parenthesization, Chain Matrix, Solution Matrix, Optimal Cost, Sequence Of Decisions, Optimal Solution |
| References: | 1. Nai-Kuan Tsao, “Error Complexity Analysis of Algorithms for Matrix Multiplication and Matrix Chain Product”, IEEE Transactions on Computers, Vol. C-30, No. 10, October 1981. 2. Thomas H. Coremen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, PHI, 2nd Edn, 2008. 3. Ellis Horowitz, Sartaj Sahani, Sanguthevar Rajasekaran, “Computer Algorithms”, University Press, 2nd Edn, 2008. 4. M.H. Alsuwaiyel , “Algorithms Design Techniques and Analysis”, PHEI, 2002. 5. David B. Wagner, “Dynamic Programming”, The Mathematica Journal, Miller Freeman Publications, 1995. 6. Phillip G. Bradfordy, Gregory J. E. Rawlinsz, Gregory E. Shannonx, “Efficient Matrix Chain Ordering in Polylog Time”, Journal of Computer, SIAM, Vol. 27, No. 2, Pp. 466 - 490, April 1998. 7. Heejo Lee, Jong Kim, Sung Je Hong, Sunggu Lee, “Processor Allocation And Task Scheduling Of Matrix Chain Products On Parallel Systems”, IEEE Transactions on Parallel and Distributed Systems, Vol. 14, No. 4, April 2003. 8. Marco Bodrato, “A Strassen-Like Matrix Multiplication Suited for Squaring And Highest Power Computation”, CIVV, 2008. 9. Muhammad Hafeez, Muhammad Younus, “An Effective Solution for Matrix Parenthesization Problem through Parallelization”, International Journal of Computers, Issue 1, Vol. 1, 2007. 10. T. C. Hu, M. T. Shirig, “Computation of Matrix Chain Products”, Stanford University, September 1981. 11. Cary Cherng, Richard E. Ladner, “Cache Efficient Simple Dynamic Programming”, ICAA, France, 2005. 12. Biswajit Bhowmik, “Design and Analysis of Algorithms”, S. K. Kataria and Sons, 1st Edition, 2011. 13. Ting Wang, “Algorithms for Parallel and Sequential Matrix-Chain Product Problem”, Ohio University, November, 1997. 14. Biswajit Bhowmik, “Dynamic Programming – Its Principles, Applications, Strengths, and Limitations”, International Journal of Engineering Science and Technology, Vol. 2(9), 2010, Pages: 4822–4826. 15. Yanhong A. Liu, Scott D. Stoller, “Dynamic Programming via Static Incrementalization”, ESOP, 1999. 16. A. R. Vasistha, “Matrices”, Krishna Publications. 17. D. Samanta, “Classic Data Structures”, PHI, 18th printing, 2010. |
| Back to the journal content | |
