Accession Number:

AD0678629

Title:

SOME TECHNIQUES FOR ALGORITHM OPTIMIZATION WITH APPLICATION TO MATRIX ARITHMETIC EXPRESSIONS

Descriptive Note:

Doctoral thesis

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1968-06-27

Pagination or Media Count:

163.0

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.

Subject Categories:

  • Theoretical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE