About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Symbolic Computation
Paper
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. © 1990, Academic Press Limited. All rights reserved.