Xavier Caruso
Chargé 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, D. Roe, T. Vaccon
Characteristic polynomials of $p$-adic matrices
prépublication (2017), 8 pages

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, D. Roe, T. Vaccon
Division and slope factorization of $p$-adic polynomials
à paraître dans les 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
Numerical stability of Euclide algorithm over ultrametric fields
à paraître à J. Number Theor. Bordeaux

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
$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 6 février 2017