Simplified Optimal Parenthesization Scheme for Matrix Chain Multiplication Problem using Bottom-up Practice in 2-Tree Structure

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 here.

Keywords

• Scalar Multiplication
• Optimal Parenthesization
• Chain Matrix
• Solution Matrix
• Optimal Cost
• Sequence of Decisions
• Optimal Solution