An Effective Solution for Matrix Parenthesization Problem through Parallelisation
Muhammad Hafeez, Muhammad Usman Younus · 2007
Dynamic programming can be used to solve the optimization problem of optimal matrix parenthesization problem, which is discussed in detail in the paper. The results and their analysis reveal that there is considerable amount of time reduction compared with simple left to right multiplication, on applying the matrix parenthesization algorithm. Time reduction varies from 0% to 96%, proportional to the number of matrices and the sequence of dimensions. It is also learnt that on applying parallel matrix parenthesization algorithm, time is reduced proportional to the number of processors at the start, however, after some increase, adding more processors does not yield any more throughput but only increases the overhead and cost. Foremost improvement of the parallel algorithm used is its independency on the number of matrices. Moreover, work has been uniformly distributed between processors, besides its confirmation to single processor algorithm results.