Fast computation of generic bivariate resultants

DOI10.1016/j.jco.2020.101499zbMath1462.13028OpenAlexW2969268864MaRDI QIDQ1996880

Joris van der Hoeven, Grégoire Lecerf

Publication date: 26 February 2021

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2020.101499

zbMATH Keywords

complexityalgorithmfinite fieldscomputer algebraresultantGroebner baseseliminationbivariate polynomialsmultipoint evaluation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Randomized algorithms (68W20) Solving polynomial systems; resultants (13P15)

Related Items

Efficient search for superspecial hyperelliptic curves of genus four with automorphism group containing \(\mathbf{C}_6\), Chinese Remainder Theorem for bivariate lexicographic Gröbner bases, Elimination ideal and bivariate resultant over finite fields, High-order lifting for polynomial Sylvester matrices, A fast randomized geometric algorithm for computing Riemann-Roch spaces, Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one

Uses Software

• Kronecker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers
• Deterministic root finding over finite fields using Graeffe transforms
• Solving bivariate systems using rational univariate representations
• Modular composition modulo triangular sets and applications
• Résolution des systèmes d'équations algébriques
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Sparse FGLM algorithms
• On the complexity of the Lickteig-Roy subresultant algorithm
• Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals
• Fast multivariate multi-point evaluation revisited
• A concise proof of the Kronecker polynomial system solver from scratch
• Modern Computer Algebra
• Fast Polynomial Factorization and Modular Composition
• Sub-cubic change of ordering for Gröbner basis
• Powers of tensors and fast matrix multiplication
• Subquadratic-time factoring of polynomials over finite fields
• On Computing the Resultant of Generic Bivariate Polynomials
• Fast construction of irreducible polynomials over finite fields