Fast computation of generic bivariate resultants

Joris van der Hoeven; Grégoire Lecerf

doi:10.1016/j.jco.2020.101499

Fast computation of generic bivariate resultants

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that the resultant of two “sufficiently generic” bivariate polynomials over a finite field can be computed in quasi-linear expected time, using a randomized algorithm of Las Vegas type. A similar complexity bound is proved for the computation of the lexicographical Gröbner basis for the ideal generated by the two polynomials.

Original language	English
Article number	101499
Journal	Journal of Complexity
Volume	62
DOIs	https://doi.org/10.1016/j.jco.2020.101499
Publication status	Published - 1 Feb 2021

Keywords

Algorithm
Complexity
Computer algebra
Elimination
Multipoint evaluation
Resultant

Access to Document

10.1016/j.jco.2020.101499

Cite this

@article{4957a94bb4d342ad98cc389fdf34cf77,

title = "Fast computation of generic bivariate resultants",

abstract = "We prove that the resultant of two “sufficiently generic” bivariate polynomials over a finite field can be computed in quasi-linear expected time, using a randomized algorithm of Las Vegas type. A similar complexity bound is proved for the computation of the lexicographical Gr{\"o}bner basis for the ideal generated by the two polynomials.",

keywords = "Algorithm, Complexity, Computer algebra, Elimination, Multipoint evaluation, Resultant",

author = "\{van der Hoeven\}, Joris and Gr{\'e}goire Lecerf",

note = "Publisher Copyright: {\textcopyright} 2020",

year = "2021",

month = feb,

day = "1",

doi = "10.1016/j.jco.2020.101499",

language = "English",

volume = "62",

journal = "Journal of Complexity",

issn = "0885-064X",

}

TY - JOUR

T1 - Fast computation of generic bivariate resultants

AU - van der Hoeven, Joris

AU - Lecerf, Grégoire

PY - 2021/2/1

Y1 - 2021/2/1

N2 - We prove that the resultant of two “sufficiently generic” bivariate polynomials over a finite field can be computed in quasi-linear expected time, using a randomized algorithm of Las Vegas type. A similar complexity bound is proved for the computation of the lexicographical Gröbner basis for the ideal generated by the two polynomials.

AB - We prove that the resultant of two “sufficiently generic” bivariate polynomials over a finite field can be computed in quasi-linear expected time, using a randomized algorithm of Las Vegas type. A similar complexity bound is proved for the computation of the lexicographical Gröbner basis for the ideal generated by the two polynomials.

KW - Algorithm

KW - Complexity

KW - Computer algebra

KW - Elimination

KW - Multipoint evaluation

KW - Resultant

U2 - 10.1016/j.jco.2020.101499

DO - 10.1016/j.jco.2020.101499

M3 - Article

AN - SCOPUS:85086161572

SN - 0885-064X

VL - 62

JO - Journal of Complexity

JF - Journal of Complexity

M1 - 101499

ER -

Fast computation of generic bivariate resultants

Abstract

Keywords

Access to Document

Fingerprint

Cite this