Fast computation of generic bivariate resultants (Q1996880): Difference between revisions

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\).