Paper Info
Title
Computing with polynomials given byblack boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators
Abstract
Algorithms are developed that adopt a novel implicit representation for multivariate polynomials and rational functions with rational coefficients, that of black boxes for their evaluation. We show that within this representation the polynomial greatest common divisor and factorization problems, as well as the problem of extracting the numerator and denominator of a rational function, can all be solved in random polynomial-time. Since we can convert black boxes efficiently to sparse format, problems with sparse solutions, e.g., sparse polynomial factorization and sparse multivariate rational function interpolation, are also in random polynomial time. Moreover, the black box representation is one of the most space efficient implicit representations that we know. Therefore, the output programs can be easily distributed over a network of processors for further manipulation, such as sparse interpolation.
Year
DOI
Venue
1988
10.1016/S0747-7171(08)80015-6
Journal of Symbolic Computation - Special issue on computational algebraic complexity
Keywords
Field
DocType
novel implicit representation,black box representation,rational coefficient,byblack box,Greatest common divisor,sparse solution,sparse polynomial factorization,multivariate polynomial,sparse interpolation,black box,sparse multivariate rational function,rational function
Discrete mathematics,Combinatorics,Polynomial,Algebra,Square-free polynomial,Irreducible fraction,Partial fraction decomposition,Polynomial greatest common divisor,Rational function,Difference polynomials,Factorization of polynomials,Mathematics
Conference
Volume
Issue
ISSN
9
3
Journal of Symbolic Computation
ISBN
Citations 
PageRank 
0-8186-0877-3
88
7.36
References 
Authors
20
2
Name
Order
Citations
PageRank
Erich Kaltofen12332261.40
Barry M. Trager261497.81