Efficient computation of Riemann–Roch spaces for plane curves with ordinary singularities

Simon Abelard; Alain Couvreur; Grégoire Lecerf

doi:10.1007/s00200-022-00588-x

Efficient computation of Riemann–Roch spaces for plane curves with ordinary singularities

Laboratoire d'Informatique (LIX)

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

Abstract

We revisit the seminal Brill–Noether algorithm for plane curves with ordinary singularities. Our new approach takes advantage of fast algorithms for polynomials and structured matrices. We design a new probabilistic algorithm of Las Vegas type that computes a Riemann–Roch space in expected sub-quadratic time.

Original language	English
Pages (from-to)	739-804
Number of pages	66
Journal	Applicable Algebra in Engineering, Communication and Computing
Volume	35
Issue number	6
DOIs	https://doi.org/10.1007/s00200-022-00588-x
Publication status	Published - 1 Nov 2024

Keywords

Algebraic curves
Complexity
Riemann–Roch spaces

Access to Document

10.1007/s00200-022-00588-x

Cite this

@article{b2dd141be15a42b78a281efb61bb4e8a,

title = "Efficient computation of Riemann–Roch spaces for plane curves with ordinary singularities",

abstract = "We revisit the seminal Brill–Noether algorithm for plane curves with ordinary singularities. Our new approach takes advantage of fast algorithms for polynomials and structured matrices. We design a new probabilistic algorithm of Las Vegas type that computes a Riemann–Roch space in expected sub-quadratic time.",

keywords = "Algebraic curves, Complexity, Riemann–Roch spaces",

author = "Simon Abelard and Alain Couvreur and Gr{\'e}goire Lecerf",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2022.",

year = "2024",

month = nov,

day = "1",

doi = "10.1007/s00200-022-00588-x",

language = "English",

volume = "35",

pages = "739--804",

journal = "Applicable Algebra in Engineering, Communication and Computing",

issn = "0938-1279",

number = "6",

}

TY - JOUR

T1 - Efficient computation of Riemann–Roch spaces for plane curves with ordinary singularities

AU - Abelard, Simon

AU - Couvreur, Alain

AU - Lecerf, Grégoire

N1 - Publisher Copyright: © The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2022.

PY - 2024/11/1

Y1 - 2024/11/1

N2 - We revisit the seminal Brill–Noether algorithm for plane curves with ordinary singularities. Our new approach takes advantage of fast algorithms for polynomials and structured matrices. We design a new probabilistic algorithm of Las Vegas type that computes a Riemann–Roch space in expected sub-quadratic time.

AB - We revisit the seminal Brill–Noether algorithm for plane curves with ordinary singularities. Our new approach takes advantage of fast algorithms for polynomials and structured matrices. We design a new probabilistic algorithm of Las Vegas type that computes a Riemann–Roch space in expected sub-quadratic time.

KW - Algebraic curves

KW - Complexity

KW - Riemann–Roch spaces

U2 - 10.1007/s00200-022-00588-x

DO - 10.1007/s00200-022-00588-x

M3 - Article

AN - SCOPUS:85143290653

SN - 0938-1279

VL - 35

SP - 739

EP - 804

JO - Applicable Algebra in Engineering, Communication and Computing

JF - Applicable Algebra in Engineering, Communication and Computing

IS - 6

ER -

Efficient computation of Riemann–Roch spaces for plane curves with ordinary singularities

Abstract

Keywords

Access to Document

Fingerprint

Cite this