Study on computer algorithms involving multiplication

Abstract

This ~esearch work has been aimed at investigating algorithms involving multiplication. In particular three classes of problems namely, polynomial evaluation, matrix multiplication and chain matrix multiplication have been considered. The problem of polynomial evaluation has been considered with preprocessing which has been proven efficient in case it is evaluated at many points. Belaga, Peterson-Stockmeyer and Knuth's method of preprocessing have been subject to numerous experiments, and Belaga's method has outperformed the remaining algorithms in terms of computational time requirement for evaluating preprocessed polynomials, whereas Belaga's preprocessing algorithm was found to be the most time consuming. Matrix multiplication algorithms were tested with both integer and real data. We have considered order of the matrices in the range 4-128 for our experiment. It was observed that in this range none of the prospective algorithms of better orders could perform better than O(nJ ) classical algorithm and algorithm using Winograd's identity. Multiplication algorithm using Winograd's identity came out superior in both the cases of integer and real data elements. This finding does not totally disagree with the previous assertion that Strassen's algorithm become competitive only after order of the involved matrices exceed 120. However, our numerical experiments do not indicate that even after the order exceeds 120 it can have any competitive edge over Winograd's identity or even classical algorithm for orders near 120. We have also introduced a new preprocessing method for converting an arbitrary system of linear equations into a positive definite linear systems for which convergent iterative schemes exist. This preprocessing was done by recursively using Strassen's scheme to compute A'A by using only two-thirds of the cost required to multiply two arbitrary matrices using Strassen's scheme. This has resulted in an algorithm with 33% savings over direct application of Strassen's multiplication scheme. For chain matrix multiplication, dynamic programming scheme as well as heuristic algorithms of Chin and Hu-Shing were considered. Both the heuristic algorithms performed very well producing optimal sequences in reasonable amount of computation with Hu-Shing's algorithm performing better. Moreover, both these methods produced solutions whose deviation from the optimal solution was found to be decreasing with the number of matrices in the chain.