On the complexity of computing integral bases of function fields
| Autor: | Simon Abelard |
|---|---|
| Přispěvatelé: | Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), David R. Cheriton School of Computer Science, University of Waterloo [Waterloo], This paper is a part of a project that has received funding by the French Agence de l'Innovation de Défense (DGA)., Boulier F., England M., Sadykov T.M., Vorozhtsov E.V. |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Algebraic function field
Computer Science - Symbolic Computation FOS: Computer and information sciences [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] 050101 languages & linguistics Plane curve [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC] 02 engineering and technology Symbolic Computation (cs.SC) Commutative Algebra (math.AC) Puiseux series Mathematics - Algebraic Geometry ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Polynomial matrices 0202 electrical engineering electronic engineering information engineering FOS: Mathematics 0501 psychology and cognitive sciences Linear algebra Algebraic Geometry (math.AG) Mathematics Discrete mathematics [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Irreducible polynomial 05 social sciences Basis (universal algebra) Function (mathematics) Mathematics - Commutative Algebra 020201 artificial intelligence & image processing [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG] Monic polynomial |
| Zdroj: | CASC 2020-Computer Algebra in Scientific Computing CASC 2020-Computer Algebra in Scientific Computing, Sep 2020, Linz / Virtual, Austria. pp.42-62, ⟨10.1007/978-3-030-60026-6_3⟩ Computer Algebra in Scientific Computing ISBN: 9783030600259 CASC |
| DOI: | 10.1007/978-3-030-60026-6_3⟩ |
| Popis: | Let $\mathcal{C}$ be a plane curve given by an equation $f(x,y)=0$ with $f\in K[x][y]$ a monic squarefree polynomial. We study the problem of computing an integral basis of the algebraic function field $K(\mathcal{C})$ and give new complexity bounds for three known algorithms dealing with this problem. For each algorithm, we study its subroutines and, when it is possible, we modify or replace them so as to take advantage of faster primitives. Then, we combine complexity results to derive an overall complexity estimate for each algorithm. In particular, we modify an algorithm due to B\"ohm et al. and achieve a quasi-optimal runtime. Comment: Preliminary version |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|