Elimination ideal and bivariate resultant over finite fields

DOI10.1145/3597066.3597100arXiv2302.08891WikidataQ131124603 ScholiaQ131124603MaRDI QIDQ6081978FDOQ6081978

Authors: Gilles Villard 

Publication date: 3 November 2023

Published in: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Abstract: A new algorithm is presented for computing the largest degree invariant factor of the Sylvester matrix (with respect either to $x$ or $y$) associated to two polynomials $a$ and $b$ in $mathbb{F}_q[x,y]$ which have no non-trivial common divisors. The algorithm is randomized of the Monte Carlo type and requires $O((de{)}^{1+epsilon}log(q{)}^{1+o(1)})$ bit operations, where $d$ an $e$ respectively bound the input degrees in $x$ and in $y$. It follows that the same complexity estimate is valid for computing: a generator of the elimination ideal $langlea,banglecapmathbb{F}_q[x]$ (or $mathbb{F}_q[y]$), as soon as the polynomial system $a=b=0$ has not roots at infinity; the resultant of $a$ and $b$ when they are sufficiently generic, especially so that the Sylvester matrix has a unique non-trivial invariant factor. Our approach is to use the reduction of the problem to a problem of minimal polynomial in the quotient algebra $mathbb{F}_q[x,y]/langlea,bangle$. By proposing a new method based on structured polynomial matrix division for computing with the elements in the quotient, we manage to improve the best known complexity bounds.

Full work available at URL: https://arxiv.org/abs/2302.08891

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Solving zero-dimensional systems through the rational univariate representation
• Title not available (Why is that?)
• Change of order for bivariate triangular sets
• On the complexity of solving bivariate systems
• Title not available (Why is that?)
• Fast polynomial factorization and modular composition
• Modular composition modulo triangular sets and applications
• Fast Algorithms for Manipulating Formal Power Series
• Title not available (Why is that?)
• Title not available (Why is that?)
• Gröbner bases and primary decomposition of polynomial ideals
• Multivariate polynomials, duality, and structured matrices
• Solving sparse linear equations over finite fields
• Fast computation of special resultants
• Title not available (Why is that?)
• Modern computer algebra
• Fast algorithms for zero-dimensional polynomial systems using duality
• Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey
• Title not available (Why is that?)
• Fast construction of irreducible polynomials over finite fields
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• Subquadratic-time factoring of polynomials over finite fields
• Title not available (Why is that?)
• Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices
• A new polynomial factorization algorithm and its implementation
• Fast construction of irreducible polynomials over finite fields
• Résolution des systèmes d'équations algébriques
• Inversion components of block Hankel-like matrices
• Displacement ranks of matrices and linear equations
• Ideal basis and primary decompositions: case of two variables
• Title not available (Why is that?)
• Discrete logarithms in \(\mathrm{GF}(p)\)
• Solving zero-dimensional algebraic systems
• Sparse FGLM algorithms
• On the complexity exponent of polynomial system solving
• Title not available (Why is that?)
• Fast parallel algorithms for matrix reduction to normal forms
• Inter-reciprocity applied to electrical networks
• Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals
• On the complexity of the Lickteig-Roy subresultant algorithm
• Sub-cubic change of ordering for Gröbner basis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast multivariate multi-point evaluation revisited
• Fast computation of generic bivariate resultants
• On Computing the Resultant of Generic Bivariate Polynomials
• Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one
• On the Complexity of Multivariate Polynomial Division
• Change of Basis for m-primary Ideals in One and Two Variables

Cited In (5)

• High-order lifting for polynomial Sylvester matrices
• Chinese Remainder Theorem for bivariate lexicographic Gröbner bases
• Elimination theory for addition and the frobenius map in polynomial rings
• Bivariate polynomial reduction and elimination ideal over finite fields
• Fast integral bases computation

This page was built for publication: Elimination ideal and bivariate resultant over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081978)