Xavier Caruso
Directeur de recherche en mathématiques au CNRS
Algorithmique p-adique

Étant donné que les nombres $p$-adiques possèdent une infinité de chiffres, il est nécessaire de les tronquer pour les manipuler sur machine. Cette remarque est à l'origine de difficultés particulières à la mise en place d'une algorithmique efficace dans un contexte $p$-adique. Les travaux présentés dans cette rubrique abordent ces questions selon plusieurs points de vue.

X. Caruso, E. Eid, R. Lercier
Fast computation of elliptic curve isogenies in characteristic two
prépublication (2020), 26 pages

We propose an algorithm that calculates isogenies between elliptic curves defined over an extension $K$ of $\mathbb{Q}_2$. It consists in efficiently solving with a logarithmic loss of $2$-adic precision the first order differential equation satisfied by the isogeny.
We give some applications, especially computing over finite fields of characteristic 2 isogenies of elliptic curves and irreducible polynomials, both in quasi-linear time in the degree.
X. Caruso, T. Vaccon, T. Verron
Signature-based algorithms for Gröbner bases over Tate algebras
prépublication (2020), 8 pages

Introduced by Tate, Tate algebras play a major role in the context of analytic geometry over the $p$-adics, where they act as a counterpart to the use of polynomial algebras in classical algebraic geometry. In a former paper, the formalism of Gröbner bases over Tate algebras has been introduced and effectively implemented. One of the bottleneck in the algorithms was the time spent on reduction, which are significantly costlier than over polynomials. In the present article, we introduce two signature-based Gröbner bases algorithms for Tate algebras, in order to avoid many reductions. They have been implemented in Sage. We discuss their superiority based on numerical evidences.
X. Caruso, T. Vaccon, T. Verron
Gröbner bases over Tate algebras
proceedings de la conférence ISSAC 2019

Tate algebras are fundamental objects in the context of analytic geometry over the $p$-adics. Roughly speaking, they play the same role as polynomial algebras play in classical algebraic geometry. In the present article, we develop the formalism of Gröbner bases for Tate algebras. We prove an analogue of the Buchberger criterion in our framework and design a Buchberger-like and a F4-like algorithm for computing Gröbner bases over Tate algebras. An implementation in Sage is also discussed.
A. Bostan, X. Caruso, P. Dumas, G. Christol
Fast coefficient computation for algebraic power series in positive characteristic
The Open Book Series 2 (2019), 119–135

Nous revenons sur le théorème de Christol sur les séries algébriques en caractéristique positive et en proposons une nouvelle démonstration. Cette démonstration, qui agence intelligemment des ingrédients dissiminés dans les autres preuves classiques (théorème de Fürstenberg, opérateur de Cartier), est particulièrement adaptée aux applications algorithmiques que nous avons en vue. Précisément, nous en tirons profit pour la conception d'un nouvel algorithme efficace pour le calcul du $N$-ième coefficient d'une série formelle donnée, algébrique sur le sous-corps des fractions rationnelles (pour un corps de base parfait de caractéristique $p$).
Notre algorithme a de nombreux avantages : il est plus général, plus natural et plus rapide que les précédents. Non seulement, sa complexité algébrique est linéaire en $\log N$ et quasi-linéaire en $p$ mais elle est aussi bien meilleure vis-à-vis des autres paramètres que dans tous les autres algorithmes qui étaient connus jusqu'à présent. De plus, lorsque le corps de base est un corps fini, notre nouvelle approche est à la base de la conception d'un algorithme encore plus rapide donc la complexité en linéaire en $\log N$ et quasi-linéaire en $\sqrt p$.
X. Caruso, D. Roe, T. Vaccon
ZpL: a $p$-adic precision package
proceedings de la conférence ISSAC 2018

Nous présentons un nouveau package pour le logiciel de calcul formel SageMath. Ce package offre une implémentation des nombres $p$-adiques avec un suivi de précision basée sur la méthode des réseaux introduites dans nos précédents articles. Les algorithmes sous-jacents sont fondées sur les méthodes de différentiation automatique. Nous les détaillons, nous étudions leur complexité et discutons de nos choix d'implémentation.
Nous illustrons les avantages de notre package (en comparaison des implémentations précédentes) à travers de nombreux exemples venant de l'algèbre linéaire, l'algèbre commutative et la théorie des équations différentielles.
X. Caruso, D. Roe, T. Vaccon
Characteristic polynomials of $p$-adic matrices
proceedings de la conférence ISSAC 2017

Nous étudions la précision optimale sur les coefficients du polynôme caractéristique $\chi(A)$ ainsi que les valeurs propres d'une matrice $A$ à coefficients $p$-adiques donnée à précision finie. Lorsque $A$ est à coefficients entiers et connue à précision $O(p^N)$, nous donnons un critère (vérifiable en temps $\tilde O(n^\omega)$) pour que la précision optimale sur $\chi(A)$ soit exactement $O(p^N)$. We donnons également un algorithme de complexité $\tilde O(n^3)$ pour déterminer la précision optimale lorsque le critère précédent n'est pas satisfait.
X. Caruso
Computations with $p$-adic numbers
Les cours du CIRM 5 (2017), Journées Nationales de Calcul Formel, https://doi.org/10.5802/ccirm.25

Ce texte contient les notes d'un cours que j'ai donné aux Journées Nationales de Calcul Formel en janvier 2017. L'objectif du cours était de discuter l'algorithmique de bas niveau pour la manipulation des nombres $p$-adiques sur ordinateur. Le cours est divisé en deux parties : dans la première, on présente et compare différents paradigmes pour l'implémentation des nombres $p$-adiques tandis que, dans la seconde, on met au point un cadre général pour étudier la propagation de la précision dans un contexte ultramétrique puis on l'applique dans plusieurs situations concrètes.
Présentation beamer du cours.
X. Caruso
Numerical stability of Euclidean algorithm over ultrametric fields
J. Number Theor. Bordeaux 29 (2017), 503–534

Nous étudions le problème de la stabilité du calcul des résultants et sous-résultants des polynômes définis sur des anneaux de valuation discrète complets. Nous démontrons que les algorithmes de type Euclide sont très instables en moyenne et, dans de nombreux cas, nous expliquons comment les rendre stables sans dégrader la complexité. Chemin faisant, nous déterminons la loi de la valuation des sous-résultants de deux polynômes $p$-adiques aléatoires unitaires de même degré.
X. Caruso, D. Roe, T. Vaccon
Division and slope factorization of $p$-adic polynomials
proceedings de la conférence ISSAC 2016

Nous étudions deux opérations importantes sur les polynômes définis sur les corps de valuation discrète complets: la division euclidienne et le factorisation. Nous concevons en particulier un algorithme simple et efficace pour le calcul de la factorisation par les pentes qui a l'avantage d'éviter de travailler avec des exposants fractionnaires. Nous portons une attention particulière à l'étude de la stabilité numérique et analysons le comportement de notre algorithme selon plusieurs modèles de précision.
X. Caruso, D. Roe, T. Vaccon
$p$-adic stability in linear algebra
proceedings de la conférence ISSAC 2015

En nous basant sur les méthodes de précision différentielle mises au point précédemment par les mêmes auteurs, nous étudions la stabilité $p$-adique des opérations usuelles sur les matrices et les espaces vectoriels. Nous montrons que les techniques à base de réseaux surpassent les méthodes naïves dans de nombreux cas pratiques comme la multiplication de matrices and la somme et l'intersection de sous-espaces vectoriels. We analysons également le calcul du déterminant, du polynôme caractéristique et de la factorisation LU. Nous complétons nos observations avec des résultats numériques.
X. Caruso
Random matrices over a DVR and LU factorization
J. Symbolic Comput. 71 (2015), 98–123

Soient $R$ un anneau de valuation discrète et $K$ son corps des fractions. Si $M$ est une matrice à coefficients dans $R$ qui admet une factorisation LU, il peut arriver que les coefficients des facteurs $L$ et $U$ ne soient pas dans $R$ mais seulement dans $K$. Pour les applications algorithmiques, il est important d'avoir un bon contrôle sur les valuations de ces coefficients. Dans cet article, nous démontrons que ces valuations ne sont pas trop grandes en moyenne. Nous utilisons ensuite ce résultat pour concevoir un algorithme efficace pour le calcul d'une base d'un faisceau cohérent sur $\mathbb A^1_K$ à partir de la connaissance de ces fibres.
X. Caruso, D. Roe, T. Vaccon
Tracking $p$-adic precision
LMS J. Comput. Math. 17 (2014), 274–294

Nous proposons une nouvelle méthode pour la propagation de la précision $p$-adique (et plus généralement ultramétrique) dans le calculs. Nous présentons également une application jouet au calcul stable de la suite SOMOS 4.
X. Caruso, D. Lubicz
Linear Algebra over $\mathbb Z_p[[u]]$ and related rings
LMS J. Comput. Math. 17 (2014), 302–344

Soit $R$ un anneau de valuation discrète complet. On pose $S = R[[u]]$ et on fixe un entier $d$ strictement positif. Le but de cet article est de donner des outils algorithmiques pour le calcul effectif de toutes les opértions classiques (somme, intersection...) sur les sous-$S$-module de $S^d$. Au cours de l'analyse de la précision, nous aurons besoin d'introduire des anneaux de coefficients plus généraux qui nous paraissent intéressants en eux-mêmes. Nos résultats sont susceptibles d'avoir des applications à la théorie d'Iwasawa et la théorie de Hodge $p$-adique.
X. Caruso, D. Lubicz
Semi-simplifiée modulo $p$ des représentations semi-stables : une approche algorithmique
prépublication (2013), 35 pages

Le but de cet article est de présenter un algorithme de complexité polynômiale pour calculer la semi-simplifiée modulo $p$ d'une $\mathbb Q_p$-représentation semi-stable du groupe de Galois absolu d'un corps $p$-adique (i.e. une extension finie de $\mathbb Q_p$). Pour ce faire, nous utilisons abondamment la théorie de Hodge $p$-adique et, en particulier, la théorie des modules de Breuil–Kisin.

Dernière modification le 14 mars 2020