Colorado State University

10/6/2005

3:30pm-4:30pm

We present a technique to reduce the computational complexity of the algorithm
embodied in a program. Our technique, which can be automated to be used in a
compiler, works for a class of programs called affine control loops, or
equivalently, equational programs over polyhedral domains. The method is
optimal in the sense that the final program has the smallest possible
polynomial complexity. We have used it to derive an O(n^{3}) program
from an O(n^{4}) formulation of an algorithm that arises in RNA
folding. Researchers in the field took over 8 years to discover the improved
algorithm. This is joint work with PhD student Gautam Gupta.

Department of Computer Science

University of Colorado Boulder

Boulder, CO 80309-0430 USA

webmaster@cs.colorado.edu

University of Colorado Boulder

Boulder, CO 80309-0430 USA

webmaster@cs.colorado.edu