# 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.

# Descriptors:

# Subject Categories:

- Theoretical Mathematics
- Computer Programming and Software