Optimization of signal processing algorithms

We optimize implementations of one-dimensional and multidimensional signal processing algorithms by rewriting subexpressions according to a set of algebraic identities. We encode the algebraic identities as conditional rules, and program hill climbing and simulated annealing search techniques to apply the rules. Both of these search techniques avoid an exponential explosion in memory usage because they only keep a single state in memory instead of building the entire tree of possible equivalent forms. We compare the effectiveness of these search techniques in optimizing implementations of one-dimensional multirate signal processing algorithms. Our prototype environment is written in Mathematica.