Relaxed algorithms for p -adic numbers

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

  • [1] Laboratoire d’Informatique UMR 7161 CNRS École polytechnique Route de Saclay 91128 Palaiseau Cedex France

Journal de Théorie des Nombres de Bordeaux (2011)

  • Volume: 23, Issue: 3, page 541-577
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Berthomieu, Jérémy, van der Hoeven, Joris, and Lecerf, Grégoire. "Relaxed algorithms for $p$-adic numbers." Journal de Théorie des Nombres de Bordeaux 23.3 (2011): 541-577. <http://eudml.org/doc/219803>.

@article{Berthomieu2011,
abstract = {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.},
affiliation = {Laboratoire d’Informatique UMR 7161 CNRS École polytechnique Route de Saclay 91128 Palaiseau Cedex France; Laboratoire d’Informatique UMR 7161 CNRS École polytechnique Route de Saclay 91128 Palaiseau Cedex France; Laboratoire d’Informatique UMR 7161 CNRS École polytechnique Route de Saclay 91128 Palaiseau Cedex France},
author = {Berthomieu, Jérémy, van der Hoeven, Joris, Lecerf, Grégoire},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {$p$-adic numbers; power series; algorithms; -adic numbers},
language = {eng},
month = {11},
number = {3},
pages = {541-577},
publisher = {Société Arithmétique de Bordeaux},
title = {Relaxed algorithms for $p$-adic numbers},
url = {http://eudml.org/doc/219803},
volume = {23},
year = {2011},
}

TY - JOUR
AU - Berthomieu, Jérémy
AU - van der Hoeven, Joris
AU - Lecerf, Grégoire
TI - Relaxed algorithms for $p$-adic numbers
JO - Journal de Théorie des Nombres de Bordeaux
DA - 2011/11//
PB - Société Arithmétique de Bordeaux
VL - 23
IS - 3
SP - 541
EP - 577
AB - 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.
LA - eng
KW - $p$-adic numbers; power series; algorithms; -adic numbers
UR - http://eudml.org/doc/219803
ER -

References

top
  1. D. Bernstein, Removing redundancy in high precision Newton iteration. Available from http://cr.yp.to/fastnewton.html, 2000. 
  2. R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series. Journal of the ACM 25 (1978), 581–595. Zbl0388.68052MR520733
  3. 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. 
  4. 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. Zbl0712.11078MR1068536
  5. D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras. Acta Informatica 28 (1991), 693–701. Zbl0766.68055MR1129288
  6. C. Durvye and G. Lecerf, A concise proof of the Kronecker polynomial system solver from scratch. Expositiones Mathematicae 26(2) (2008), 101 – 139. Zbl1134.14317MR2413831
  7. S. De Smedt, p -adic arithmetic. The Mathematica Journal 9(2) (2004), 349–357. 
  8. A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory. Philos. Trans. Roy. Soc. London. Ser. A. 248 (1956), 407–432. Zbl0070.03502MR74349
  9. 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. Zbl1179.68198MR2402428
  10. T. Granlund et al, GMP, the GNU multiple precision arithmetic library. Available from http://www.swox.com/gmp, 1991. 
  11. J. von zur Gathen, Hensel and Newton methods in valuation rings. Math. Comp., 42(166) (1984), 637–661. Zbl0581.13001MR736459
  12. J. von zur Gathen and J. Gerhard, Modern computer algebra. Cambridge University Press, Cambridge, second edition, 2003. Zbl1055.68168MR2001757
  13. J. van der Hoeven et al, Mathemagix. Available from http://www.mathemagix.org, 2002. 
  14. W. B. Hart and D. Harvey, FLINT 1.5.1: Fast library for number theory. Available from http://www.flintlib.org, 2009. 
  15. 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. Zbl0932.68135
  16. J. van der Hoeven, Fast evaluation of holonomic functions. Theoretical Computer Science, 210 (1999), 199–215. Zbl0912.68081MR1650888
  17. J. van der Hoeven, Fast evaluation of holonomic functions near and in singularities. J. Symbolic Comput. 31 (2001), 717–743. Zbl0982.65024MR1834006
  18. J. van der Hoeven, Relax, but don’t be too lazy. J. Symbolic Comput. 34(6) (2002), 479–542. Zbl1011.68189MR1943041
  19. J. van der Hoeven, Efficient accelero-summation of holonomic functions. J. Symbolic Comput. 42(4) (2007), 389–428. Zbl1125.34072MR2317557
  20. J. van der Hoeven, New algorithms for relaxed multiplication. J. Symbolic Comput., 42(8) (2007), 792–802. Zbl1130.68103MR2345837
  21. J. van der Hoeven, Relaxed resolution of implicit equations. Technical report, HAL, 2009. http://hal.archives-ouvertes.fr/hal-00441977/fr/. 
  22. J. van der Hoeven, Newton’s method and FFT trading. J. Symbolic Comput. 45(8) (2010), 857–878. Zbl1192.13017MR2657669
  23. S. Katok, p -adic analysis compared with real. Student Mathematical Library 37. American Mathematical Society, Providence, RI, 2007. Zbl1147.12003MR2298943
  24. N. Koblitz, p -adic numbers, p -adic analysis, and zeta-functions. Graduate Texts in Mathematics 58. Springer-Verlag, New York, second edition, 1984. Zbl0364.12015MR754003
  25. S. Lang, Algebra. Graduate Texts in Mathematics 211. Springer-Verlag, third edition, 2002. Zbl0984.00001MR1878556
  26. The PARI Group, Bordeaux, PARI/GP, version 2.3.5, 2008. Available from http://pari.math.u-bordeaux.fr/. 
  27. W. A. Stein et al, Sage Mathematics Software (Version 4.2.1). The Sage Development Team, 2009. Available from http://www.sagemath.org. 
  28. A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen. Computing 7 (1971), 281–292. Zbl0223.68007MR292344
  29. 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. Zbl0563.12013MR779119

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.