All Algebraic Functions Can Be Computed Fast

Abstract

The expansions of algebraic functions can be computed 'fast' using the Newton Polygon Process and any 'normal' iteration. Let M(j) be the number of operations sufficient to multiply two jth degree polynomials. It is shown that the first N terms of an expansion of any algebraic function defined by an nth degree polynomial can be computed in O(n(M(N)) operations, while the classical method needs O(N sup n) operations. Among the numerous applications of algebraic functions are symbolic mathematics and combinatorial analysis. Reversion, reciprocation, and nth root of a polynomial are all special cases of algebraic functions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1976
Accession Number
ADA032345

Entities

People

  • H. T. Kung
  • Joseph F. Traub

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algebraic Functions
  • Algebraic Geometry
  • Algorithms
  • Arithmetic
  • Coefficients
  • Combinatorial Analysis
  • Complex Numbers
  • Computations
  • Computer Science
  • Computers
  • Iterations
  • Mathematics
  • Number Theory
  • Numbers
  • Polynomials
  • Power Series
  • Theorems

Fields of Study

  • Mathematics

Readers

  • Approximation Theory.
  • Linear Algebra