Some techniques for algorithm optimization with application to matrix arithmetic expressions
Robert A. Wagner · 1968
Abstract : 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.