1. Sub-quadratic time for Riemann-Roch spaces. The case of smooth divisors over nodal plane projective curves
- Author
-
Alain Couvreur, Grégoire Lecerf, Simon Abelard, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Geometry, arithmetic, algorithms, codes and encryption (GRACE), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This paper is a part of a project that has received funding by the French Agence de l'Innovation de Défense (DGA)., Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Inria Saclay - Ile de France, Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), and Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)
- Subjects
Projective curve ,[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Pure mathematics ,Basis (linear algebra) ,Plane (geometry) ,010102 general mathematics ,MathematicsofComputing_NUMERICALANALYSIS ,010103 numerical & computational mathematics ,Space (mathematics) ,01 natural sciences ,Riemann hypothesis ,symbols.namesake ,Mathematics::Algebraic Geometry ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,symbols ,Algebraic curve ,[MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG] ,0101 mathematics ,Projective test ,Time complexity ,Mathematics - Abstract
International audience; 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.
- Published
- 2020