Automated Formula Generation and Performance Learning for the FFT

Abstract

A single signal processing algorithm can be represented by many different but mathematically equivalent formulas. When these formulas are implemented in actual code, they often have very different running times. Thus, an important problem is finding a formula that implements the signal processing algorithm as efficiently as possible. In this paper we present three major results toward this goal: (1) Different but mathematically equivalent formulas can be generated automatically in a principled way, (2) Simple features describing formulas can be used to distinguish formulas with significantly different running times, and (3) A function approximator can learn to accurately predict the running time of a formula given a limited set of training data.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2000
Accession Number
ADA377113

Entities

People

  • Bryan Singer
  • Manuela M. Veloso

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Autonomy

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Cost Models
  • Costs
  • Errors
  • Generators
  • Heuristic Methods
  • Learning
  • Machine Learning
  • Neural Networks
  • Signal Processing
  • Standards
  • Statistical Sampling
  • Template Patterns
  • Test Sets
  • Training

Fields of Study

  • Computer science
  • Engineering

Readers

  • Approximation Theory.
  • Computer Science.
  • Neural Network Machine Learning.