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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Numéro d'article	101499
journal	Journal of Complexity
Volume	62
Les DOIs	https://doi.org/10.1016/j.jco.2020.101499
état	Publié - 1 févr. 2021

Accès au document

10.1016/j.jco.2020.101499

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@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

UR - https://www.scopus.com/pages/publications/85086161572

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

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation