, )) operations in K . Once done, every element in the basis can be represented by a vector of polynomials in K [x] whose degrees are bounded by E. To put the above integral basis in triangular form, it suffices to compute a Hermite Normal Form of a full rank n × n polynomial matrix. Using [17, Theorem 1.2] an algorithm by Labahn, Neiger and Zhou performs this task in O(n ??1 M (?)) operations in K . We can finally apply Proposition 11 and deduce the minimal local contribution for the factor ? in O, the denominators is bounded a priori by E := E(f ) + max 1?i?r c i so we can truncate all series beyond this exponent. Indeed, forgetting the higher order terms amounts to subtracting each
The complexity of solving linear equations over a finite ring, Annual Symposium on Theoretical Aspects of Computer Science, pp.472-484, 2005. ,
Computation of integral bases, Journal of Number Theory, vol.165, pp.382-407, 2016. ,
, Computing integral bases via localization and Hensel lifting, 2015.
Andreas Steenpaß, and Stefan Steidel. Parallel algorithms for normalization, Journal of Symbolic Computation, vol.51, pp.99-114, 2013. ,
Algorithmes efficaces en calcul formel, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01431717
On the complexity of solving linear congruences and computing nullspaces modulo a constant, 2012. ,
Local analytic geometry: Basic theory and applications, 2013. ,
About a new method for computing in algebraic number fields, European Conference on Computer Algebra, pp.289-290, 1985. ,
On arithmetic and the discrete logarithm problem in class groups of curves. Habilitation, 2009. ,
Rational Puiseux expansions, Compositio mathematica, vol.70, issue.2, pp.119-154, 1989. ,
Computing Riemann-Roch spaces in algebraic function fields and related topics, Journal of Symbolic Computation, vol.33, issue.4, pp.425-445, 2002. ,
An algorithm for computing an integral basis in an algebraic function field, Journal of Symbolic Computation, vol.18, issue.4, pp.353-363, 1994. ,
A reduction algorithm for algebraic function fields, 2008. ,
Computing an integral basis for an algebraic function field, 2015. ,
Directed evaluation. working paper or preprint, 2018. ,
Fast polynomial factorization and modular composition, SIAM Journal on Computing, vol.40, issue.6, pp.1767-1802, 2011. ,
Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix, Journal of Complexity, vol.42, pp.44-71, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01345627
Powers of tensors and fast matrix multiplication, Proceedings of the 39th international symposium on symbolic and algebraic computation, pp.296-303, 2014. ,
A fast algorithm for computing the truncated resultant, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pp.341-348, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01366386
Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pp.365-372, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01266014
Computing Puiseux series: a fast divide and conquer algorithm, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01578214
Algorithms for manipulating algebraic functions, 1976. ,
Integration of algebraic functions, 1984. ,
Algebraic curves, 1950. ,
Ein algorithmus zur berechnung einer minimalbasis über gegebener ordnung, Funktionalanalysis Approximationstheorie Numerische Mathematik, pp.90-103, 1967. ,