SOME TECHNIQUES FOR ALGORITHM OPTIMIZATION WITH APPLICATION TO MATRIX ARITHMETIC EXPRESSIONS
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Algorithm optimization can be accomplished by an exhaustive search over alternative algorithms for performing some programming task. The resulting algorithms are optimum only with respect to a program technology--the particular set of alternatives investigated. Thus, larger program technologies can be expected to yield better algorithms. This thesis contributes to the production of optimum algorithms in two ways. First, a technique loop-fusion was developed for producing new algorithms equivalent to old algorithms, and thus expanding program technologies. Second, a technique comparison is described which reduces the effort required by certain exhaustive searches over well- structured search spaces. These techniques are applied to the production of algorithms for evaluating matrix arithmetic expressions MAE. The operators, and , in such arithmetic expressions are interpreted as matrix addition and multiplication, respectively. A method is described for producing, for any MAE, an algorithm for its evaluation which requires fewest arrays for holding N by N matrices, while not requiring more execution time than the standard MAE evaluation algorithm. Although the algorithm-production method used is basically an exhaustive-search over a large space of program alternatives for each subexpression of the given MAE, the effort this method requires grows only linearly with the number of operators in the given expression.
- Theoretical Mathematics
- Computer Programming and Software