Relaxed algorithms for $p$-adic numbers

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

¹ 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)

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.

Résumé

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.

Détail

DOI : 10.5802/jtnb.777

Classification : 68W30, 11Y40, 11Y16
Keywords: $p$-adic numbers, power series, algorithms