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)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption

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.

Domaines: Calcul formel [cs.SC]; Géométrie algébrique [math.AG]; Complexité [cs.CC]

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⟩