Fast computation of generic bivariate resultants
The article describes a method for computing the result of two polynomials \(P,Q\) over a finite field \(\mathbb F_q\) in quasi-linear expected time using a randomized algorithm of Las Vegas type. Specifically, the expected time is \(O((de\log q)^{1+\epsilon})+\tilde O(d^2\log q)\), where \(d\geq e\) are the degrees of the polynomials and \(\epsilon\) is a fixed rational number. Theory and method rely on several well-known techniques and results in computer algebra: \begin{itemize} \item Gröbner basis computation with respect to a lexicographic ordering. For details, the article refers the reader to \textit{J. van der Hoeven} and \textit{R. Larrieu} [Appl. Algebra Eng. Commun. Comput. 30, No. 6, 509--539 (2019; Zbl 1451.13084)], but the results are summarized rather extensively in Section 3, and relies on \(P,Q\) being in a form called ``grevlex-lex-generic position, which is defined in Section 1. An element of the Gröbner basis will be in terms of \(x\) only; this is the minimal polynomial of the \(\mathbb F_q\)-linear multiplication map, which they use to deduce the resultant. \item For reduction to bivariate modular composition: \begin{itemize} \item Wiedemann's algorithm; \item Berlekamp-Massey algorithm. \end{itemize} \item For reduction to multipoint evaluation: \begin{itemize} \item Kronecker segmentation; \item evaluation-interpolation; \item straight-line programs; \end{itemize} \item For the multivariate multipoint evaluation, algorithms by Kedlaya and Umans. \end{itemize} The authors provide further notes and avenues for extension. There do not seem to be any efficient implementations of the Kedlaya and Umans algorithms [\textit{K. S. Kedlaya} and \textit{C. Umans}, SIAM J. Comput. 40, No. 6, 1767--1802 (2011; Zbl 1333.11117)] at the present time, so they do not expect practical implementations of this approach soon. Chinese remaindering and rational reconstruction would extend these techniques to \(\mathbb Q\).
- On computing the resultant of generic bivariate polynomials
- Probabilistic algorithms for computing resultants
- Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals
- Fast computation of the Bézout and Dixon resultant matrices
- Improved algorithms for computing determinants and resultants
- A concise proof of the Kronecker polynomial system solver from scratch
- A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers
- Deterministic root finding over finite fields using Graeffe transforms
- Efficient computation of zero-dimensional Gröbner bases by change of ordering
- Fast construction of irreducible polynomials over finite fields
- Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals
- Fast multivariate multi-point evaluation revisited
- Fast polynomial factorization and modular composition
- scientific article; zbMATH DE number 3465689 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 2151179 (Why is no real title available?)
- Modern computer algebra
- Modular composition modulo triangular sets and applications
- On computing the resultant of generic bivariate polynomials
- On the complexity of the Lickteig-Roy subresultant algorithm
- Powers of tensors and fast matrix multiplication
- Résolution des systèmes d'équations algébriques
- Solving bivariate systems using rational univariate representations
- Sparse FGLM algorithms
- Sub-cubic change of ordering for Gröbner basis: a probabilistic approach
- Subquadratic-time factoring of polynomials over finite fields
- Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one
- Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals
- Fast computation of special resultants
- A fast algorithm for computing the truncated resultant
- scientific article; zbMATH DE number 1253989 (Why is no real title available?)
- Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals
- A fast randomized geometric algorithm for computing Riemann-Roch spaces
- On computing the resultant of generic bivariate polynomials
- Implementations of efficient univariate polynomial matrix algorithms and application to bivariate resultants
- Probabilistic algorithms for computing resultants
- 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
- Bivariate polynomial reduction and elimination ideal over finite fields
- Faster modular composition
This page was built for publication: Fast computation of generic bivariate resultants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1996880)
