Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 296-305
- https://doi.org/10.1109/sfcs.1988.21946
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. It is shown that within this evaluation-box 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 be solved in random polynomial time in the usual parameters. Since the resulting evaluation programs for the goal polynomials can be converted efficiently to sparse format, solutions to sparse problems such as the sparse ration interpolation problem follow as a consequence.Keywords
This publication has 17 references indexed in Scilit:
- Improved sparse multivariate polynomial interpolation algorithmsPublished by Springer Nature ,1989
- DagwoodACM Transactions on Mathematical Software, 1988
- Greatest common divisors of polynomials given by straight-line programsJournal of the ACM, 1988
- Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomialsPublished by Association for Computing Machinery (ACM) ,1987
- Uniform closure properties of P-computable functionsPublished by Association for Computing Machinery (ACM) ,1986
- Factoring sparse multivariate polynomialsJournal of Computer and System Sciences, 1985
- Effective Hilbert irreducibilityInformation and Control, 1985
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial FactorizationSIAM Journal on Computing, 1985
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- Factorization of PolynomialsPublished by Springer Nature ,1982