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.

A. Bostan, X. Caruso, P. Dumas, G. Christol
Fast coefficient computation for algebraic power series in positive characteristic
prépublication (2018)

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
prépublication (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
notes de cours (2017), 83 pages

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 17 novembre 2018