Relaxed algorithms for $p$-adic numbers

Jérémy Berthomieu; Joris van der Hoeven; Grégoire Lecerf

doi:10.5802/jtnb.777

Relaxed algorithms for

p

-adic numbers

Jérémy Berthomieu ¹ ; Joris van der Hoeven ¹ ; Grégoire Lecerf ¹

¹ Laboratoire d’Informatique UMR 7161 CNRS École polytechnique Route de Saclay 91128 Palaiseau Cedex France

Journal de théorie des nombres de Bordeaux, Tome 23 (2011) no. 3, pp. 541-577.

Abstract (VO)
Résumé

Current implementations of $p$ -adic numbers usually rely on so called zealous algorithms, which compute with truncated $p$ -adic expansions at a precision that can be specified by the user. In combination with Newton-Hensel type lifting techniques, zealous algorithms can be made very efficient from an asymptotic point of view.

In the similar context of formal power series, another so called lazy technique is also frequently implemented. In this context, a power series is essentially a stream of coefficients, with an effective promise to obtain the next coefficient at every stage. This technique makes it easier to solve implicit equations and also removes the burden of determining appropriate precisions from the user. Unfortunately, naive lazy algorithms are not competitive from the asymptotic complexity point of view. For this reason, a new relaxed approach was proposed by van der Hoeven in the 90’s, which combines the advantages of the lazy approach with the asymptotic efficiency of the zealous approach.

In this paper, we show how to adapt the lazy and relaxed approaches to the context of $p$ -adic numbers. We report on our implementation in the C++ library algebramix of Mathemagix, and show significant speedups in the resolution of $p$ -adic functional equations when compared to the classical Newton iteration.

Les implantations actuelles des nombres $p$ -adiques reposent essentiellement sur des techniques dites zélées, où la précision de calcul doit être fixée à l’avance par l’utilisateur. Cette approche est très efficace du point de vue de la complexité asymptotique et elle est largement utilisée, par exemple dans des algorithmes de remontée de type Newton–Hensel.

Dans le contexte similaire des séries formelles, il existe des techniques alternatives, appelées paresseuses, qui ont l’avantage d’être plus naturelles : une série formelle y est représentée comme une suite de coefficients munie d’une méthode pour calculer le coefficient suivant et ce, à tout ordre. Cette approche facilite grandement la résolution d’équations implicites et retire tout soucis de choix de la précision des calculs à l’utilisateur. Pendant longtemps cette approche paresseuse était pénalisée par son manque d’efficacité. Les premières variantes rapides ont été développées dans les années 90 par van der Hoeven, et portent désormais la terminologie d’algorithmes détendus : ceux-ci combinent le confort de l’approche paresseuse avec l’efficacité des méthodes zélées.

Dans ce papier, nous montrons comment adapter l’algorithmique détendue des séries au cas des nombres $p$ -adiques. Nos implantations sont disponibles dans la bibliothèque C++ algebramix de Mathemagix. Comparés à une itération de Newton classique, nous obtenons des gains de performances significatifs pour la résolution de certaines équations fonctionnelles $p$ -adiques.

MR Zbl

DOI : 10.5802/jtnb.777

Classification : 68W30, 11Y40, 11Y16
Keywords:

p

-adic numbers, power series, algorithms

Affiliations des auteurs :

Jérémy Berthomieu ¹ ; Joris van der Hoeven ¹ ; Grégoire Lecerf ¹

¹ Laboratoire d’Informatique UMR 7161 CNRS École polytechnique Route de Saclay 91128 Palaiseau Cedex France

@article{JTNB_2011__23_3_541_0,
     author = {J\'er\'emy Berthomieu and Joris van der Hoeven and Gr\'egoire Lecerf},
     title = {Relaxed algorithms for $p$-adic numbers},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {541--577},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {23},
     number = {3},
     year = {2011},
     doi = {10.5802/jtnb.777},
     mrnumber = {2861075},
     zbl = {1247.11152},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.777/}
}

TY  - JOUR
AU  - Jérémy Berthomieu
AU  - Joris van der Hoeven
AU  - Grégoire Lecerf
TI  - Relaxed algorithms for $p$-adic numbers
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2011
SP  - 541
EP  - 577
VL  - 23
IS  - 3
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.777/
DO  - 10.5802/jtnb.777
LA  - en
ID  - JTNB_2011__23_3_541_0
ER  -

%0 Journal Article
%A Jérémy Berthomieu
%A Joris van der Hoeven
%A Grégoire Lecerf
%T Relaxed algorithms for $p$-adic numbers
%J Journal de théorie des nombres de Bordeaux
%D 2011
%P 541-577
%V 23
%N 3
%I Société Arithmétique de Bordeaux
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.777/
%R 10.5802/jtnb.777
%G en
%F JTNB_2011__23_3_541_0

Jérémy Berthomieu; Joris van der Hoeven; Grégoire Lecerf. Relaxed algorithms for $p$-adic numbers. Journal de théorie des nombres de Bordeaux, Tome 23 (2011) no. 3, pp. 541-577. doi : 10.5802/jtnb.777. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.777/

Bibliographie
Cité par

[Ber00] D. Bernstein, Removing redundancy in high precision Newton iteration. Available from http://cr.yp.to/fastnewton.html, 2000.

[BK78] R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series. Journal of the ACM 25 (1978), 581–595. | MR | Zbl

[Bre76] R. P. Brent, The complexity of multiprecision arithmetic. In R. S. Anderssen and R. P. Brent, editors, Complexity of computational problem solving, 126–165. University of Queensland Press, Brisbane, 1976.

[CC90] D. V. Chudnovsky and G. V. Chudnovsky, Computer algebra in the service of mathematical physics and number theory (Computers in mathematics, Stanford, Ca, 1986). In Lect. Notes in Pure and Applied Math. 125, 109–232. Dekker, New-York, 1990. | MR | Zbl

[CK91] D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras. Acta Informatica 28 (1991), 693–701. | MR | Zbl

[DL08] C. Durvye and G. Lecerf, A concise proof of the Kronecker polynomial system solver from scratch. Expositiones Mathematicae 26(2) (2008), 101 – 139. | MR | Zbl

[DS04] S. De Smedt, $p$ -adic arithmetic. The Mathematica Journal 9(2) (2004), 349–357.

[FS56] A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory. Philos. Trans. Roy. Soc. London. Ser. A. 248 (1956), 407–432. | MR | Zbl

[Für07] M. Fürer, Faster integer multiplication. In Proceedings of the Thirty-Ninth ACM Symposium on Theory of Computing (STOC 2007), 57–66, San Diego, California, 2007. | MR | Zbl

[G+91] T. Granlund et al, GMP, the GNU multiple precision arithmetic library. Available from http://www.swox.com/gmp, 1991.

[Gat84] J. von zur Gathen, Hensel and Newton methods in valuation rings. Math. Comp., 42(166) (1984), 637–661. | MR | Zbl

[GG03] J. von zur Gathen and J. Gerhard, Modern computer algebra. Cambridge University Press, Cambridge, second edition, 2003. | MR | Zbl

[H+02] J. van der Hoeven et al, Mathemagix. Available from http://www.mathemagix.org, 2002.

[HH09] W. B. Hart and D. Harvey, FLINT 1.5.1: Fast library for number theory. Available from http://www.flintlib.org, 2009.

[Hoe97] J. van der Hoeven, Lazy multiplication of formal power series. In W. W. Küchlin, editor, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (ISSAC 1997), 17–20, Maui, Hawaii, July 1997. | Zbl

[Hoe99] J. van der Hoeven, Fast evaluation of holonomic functions. Theoretical Computer Science, 210 (1999), 199–215. | MR | Zbl

[Hoe01] J. van der Hoeven, Fast evaluation of holonomic functions near and in singularities. J. Symbolic Comput. 31 (2001), 717–743. | MR | Zbl

[Hoe02] J. van der Hoeven, Relax, but don’t be too lazy. J. Symbolic Comput. 34(6) (2002), 479–542. | MR | Zbl

[Hoe07a] J. van der Hoeven, Efficient accelero-summation of holonomic functions. J. Symbolic Comput. 42(4) (2007), 389–428. | MR | Zbl

[Hoe07b] J. van der Hoeven, New algorithms for relaxed multiplication. J. Symbolic Comput., 42(8) (2007), 792–802. | MR | Zbl

[Hoe09] J. van der Hoeven, Relaxed resolution of implicit equations. Technical report, HAL, 2009. | HAL

[Hoe10] J. van der Hoeven, Newton’s method and FFT trading. J. Symbolic Comput. 45(8) (2010), 857–878. | MR | Zbl

[Kat07] S. Katok, $p$ -adic analysis compared with real. Student Mathematical Library 37. American Mathematical Society, Providence, RI, 2007. | MR | Zbl

[Kob84] N. Koblitz, $p$ -adic numbers, $p$ -adic analysis, and zeta-functions. Graduate Texts in Mathematics 58. Springer-Verlag, New York, second edition, 1984. | MR | Zbl

[Lan02] S. Lang, Algebra. Graduate Texts in Mathematics 211. Springer-Verlag, third edition, 2002. | MR | Zbl

[PAR08] The PARI Group, Bordeaux, PARI/GP, version 2.3.5, 2008. Available from http://pari.math.u-bordeaux.fr/.

[S+09] W. A. Stein et al, Sage Mathematics Software (Version 4.2.1). The Sage Development Team, 2009. Available from http://www.sagemath.org.

[SS71] A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen. Computing 7 (1971), 281–292. | MR | Zbl

[Wan84] P. S. Wang, Implementation of a $p$ -adic package for polynomial factorization and other related operations. In EUROSAM 84 (Cambridge, 1984), Lecture Notes in Comput. Sci. 174, 86–99. Springer, Berlin, 1984. | MR | Zbl

Avinash Kulkarni Solving p-adic polynomial systems via iterative eigenvector algorithms, Linear and Multilinear Algebra, Volume 70 (2022) no. 4, p. 650 | DOI:10.1080/03081087.2020.1743633
Joris van der Hoeven; Grégoire Lecerf On the Complexity Exponent of Polynomial System Solving, Foundations of Computational Mathematics, Volume 21 (2021) no. 1, p. 1 | DOI:10.1007/s10208-020-09453-0
Christopher Doris Exact p-adic computation in Magma, Journal of Symbolic Computation, Volume 104 (2021), p. 476 | DOI:10.1016/j.jsc.2020.08.005
Xavier Caruso; Tristan Vaccon; Thibaut Verron, Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation (2021), p. 67 | DOI:10.1145/3452143.3465521
Xavier Dahan; Tristan Vaccon, Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (2020), p. 114 | DOI:10.1145/3373207.3404045
Joris Van Der Hoeven; Grégoire Lecerf; Guillaume Quintin Modular SIMD arithmetic in M athemagix, ACM Transactions on Mathematical Software, Volume 43 (2017) no. 1, p. 1 | DOI:10.1145/2876503
Romain Lebreton; Éric Schost A simple and fast online power series multiplication and its analysis, Journal of Symbolic Computation, Volume 72 (2016), p. 231 | DOI:10.1016/j.jsc.2015.03.001
Romain Lebreton Relaxed Hensel lifting of triangular sets, Journal of Symbolic Computation, Volume 68 (2015), p. 230 | DOI:10.1016/j.jsc.2014.09.012
Hsing-Hau Chen; Ming-Deh Huang, Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation (2015), p. 109 | DOI:10.1145/2755996.2756675
Xavier Caruso; David Roe; Tristan Vaccon Tracking -adic precision, LMS Journal of Computation and Mathematics, Volume 17 (2014) no. A, p. 274 | DOI:10.1112/s1461157014000357
Pascal Giorgi; Romain Lebreton, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (2014), p. 202 | DOI:10.1145/2608628.2608647
Joris van der Hoeven, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (2014), p. 405 | DOI:10.1145/2608628.2608657
Jérémy Berthomieu; Grégoire Lecerf; Guillaume Quintin Polynomial root finding over local rings and application to error correcting codes, Applicable Algebra in Engineering, Communication and Computing, Volume 24 (2013) no. 6, p. 413 | DOI:10.1007/s00200-013-0200-5
Jérémy Berthomieu; Romain Lebreton, Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation (2012), p. 59 | DOI:10.1145/2442829.2442842

Cité par 14 documents. Sources : Crossref