Skip to Main content Skip to Navigation
Conference papers

Sub-quadratic time for Riemann-Roch spaces. The case of smooth divisors over nodal plane projective curves

Simon Abelard 1 Alain Couvreur 2 Grégoire Lecerf 1
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : We revisit the seminal Brill-Noether algorithm in the rather generic situation of smooth divisors over a nodal plane projective curve. Our approach takes advantage of fast algorithms for polynomials and structured matrices. We reach sub-quadratic time for computing a basis of a Riemann-Roch space. This improves upon previously known complexity bounds.
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/hal-02477371
Contributor : Simon Abelard <>
Submitted on : Thursday, February 13, 2020 - 12:26:37 PM
Last modification on : Friday, April 30, 2021 - 10:05:04 AM
Long-term archiving on: : Thursday, May 14, 2020 - 3:11:36 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

Citation

Simon Abelard, Alain Couvreur, Grégoire Lecerf. Sub-quadratic time for Riemann-Roch spaces. The case of smooth divisors over nodal plane projective curves. ISSAC 2020 - 45th International Symposium on Symbolic and Algebraic Computation, Jul 2020, Kalamata, Greece. pp.14-21, ⟨10.1145/3373207.3404053⟩. ⟨hal-02477371⟩

Share

Metrics

Record views

337

Files downloads

463