Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on the Number of Multiplications and Divisions

Zvi M. Kedem

Research output: Contribution to journalArticlepeer-review

Abstract

A new method for estabhshlng lower bounds on the number of multlphcatlons and divisions reqmred to compute rational functions is described The method is based on combining two known methods, dlmenstonahty and rate of growth The method is apphed to several problems and new lower bounds are obtained.

Original languageEnglish (US)
Pages (from-to)582-601
Number of pages20
JournalJournal of the ACM (JACM)
Volume26
Issue number3
DOIs
StatePublished - Jul 1 1979

Keywords

  • algebraic operations
  • analysts of algorithms
  • computational complexity
  • counting methods
  • dimensionality
  • lower bounds
  • multiplications
  • optimality
  • polynomials
  • rate of growth
  • rational functions

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on the Number of Multiplications and Divisions'. Together they form a unique fingerprint.

Cite this