Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators

DOI10.1016/S0747-7171(08)80015-6zbMath0712.12001OpenAlexW1974321539MaRDI QIDQ923629

Barry M. Trager, Erich L. Kaltofen

Publication date: 1990

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0747-7171(08)80015-6

zbMATH Keywords

algorithmsGCDfactorizationmultivariate polynomialsrandom polynomial time

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials in number theory (11C08) Polynomials in real and complex fields: factorization (12D05) Computational methods for problems pertaining to field theory (12-08)

Related Items

Derandomization and absolute reconstruction for sums of powers of linear forms, Early termination in sparse interpolation algorithms, Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases, Black-box polynomial resultants, Factoring multivariate polynomials via partial differential equations, Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits, Efficient matrix preconditioners for black box linear algebra, Sparse polynomial interpolation based on diversification, A tight relationship between generic oracles and type-2 complexity theory, Univariate polynomial factorization over finite fields, Sparse shifts for univariate polynomials, A New Black Box Factorization Algorithm - the Non-monic Case, New Sparse Multivariate Polynomial Factorization Algorithms over Integers, Factoring multivariate polynomials represented by black boxes: a Maple + C implementation, Equality in computer algebra and beyond., Interpolation of dense and sparse rational functions and other improvements in \texttt{FireFly}, Unnamed Item, Balancing act: multivariate rational reconstruction for IBP, Computing real radicals and \(S\)-radicals of polynomial systems, Sparse interpolation of multivariate rational functions, A note on Gao's algorithm for polynomial factorization, Reconstructing rational functions with \texttt{FireFly}, Improved dense multivariate polynomial factorization algorithms, Random arithmetic formulas can be reconstructed efficiently, Foreword, A fast parallel sparse polynomial GCD algorithm, Symbolic-numeric sparse interpolation of multivariate polynomials, An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation, Improved algorithms for computing determinants and resultants, Unnamed Item, On the complexity of noncommutative polynomial factorization, Average-case linear matrix factorization and reconstruction of low width algebraic branching programs, Factorization of polynomials given by arithmetic branching programs, Geometric complexity theory V: Efficient algorithms for Noether normalization, Reconstructing Algebraic Functions from Mixed Data, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, Equivalence of polynomial identity testing and polynomial factorization

Uses Software

• Dagwood

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interpolating polynomials from their values
• Factoring sparse multivariate polynomials
• Irreducibility of multivariate polynomials
• Reducibility by algebraic projections
• The complexity of partial derivatives
• Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen
• Parallel Algorithms for Algebraic Problems
• Factoring Polynomials over Algebraic Number Fields
• A taxonomy of problems with fast parallel algorithms
• Effective Hilbert irreducibility
• Representations and Parallel Computations for Rational Functions
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Solving sparse linear equations over finite fields
• A Simple Homotopy Method for Determining all Isolated Solutions to Polynomial Systems
• Greatest common divisors of polynomials given by straight-line programs
• Numerically determining solutions of systems of polynomial equations
• Multivariate Polynomial Factorization
• Finding all solutions to polynomial systems and other systems of equations
• Dagwood
• The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis