Xavier Caruso
Chargé de recherche en mathématiques au CNRS
Polynômes de Ore

Les résultats présentés dans cette rubrique concernent les polynômes de Ore qui sont une variante non commutative des polynômes classiques qui interviennent en algèbre semi-linéaire et en théorie des équations différentielles linéaires. Leurs propriétés de factorisation sont particulièrement intéressantes car elles correspondent à des énoncés de décomposition d'opérateurs semi-linéaires ou de modules à connexion.

X. Caruso, J. Le Borgne
Fast multiplication for skew polynomials
prépublication (2017), 8 pages

Dans cet article, nous décrivons un algorithme pour la multiplication rapide des polynômes tordus dont la brique de base est un algorithme de multiplication rapide modulaire qui repose sur une stratégie d'évaluation-interpolation sur une base normale. Nos algorithmes améliorent les meilleures complexités connus pour ces problèmes et sont asymptotiquement quasi-optimaux pour les grands degrés. Nous présentons également une variante de notre algorithme pour la multiplication en petit degré et expliquons comment nos résultats permettent d'améliorer la complexité d'autres questions arithmétiques portant sur les polynômes tordus.
A. Bostan, X. Caruso, É. Schost
Computation of the similarity class of the $p$-curvature
proceedings de la conférence ISSAC 2016

La $p$-courbure d'un système d'équations différentielles en caractéristique $p$ est une matrice qui mesure à quel point le système est loin d'avoir une matrice fondamentale de solutions polynomials. Nous démontrons que la classe de similitude de la $p$-courbure peut-être déterminée sans calculer la $p$-courbure elle-même. Plus précisément, nous concevons un algorithme qui calcul les invariants de similitude de la $p$-courbure en temps quasi-linéaire en $\sqrt p$. C'est nettement inférieur à la taille de la $p$-courbure, qui généralement croît de manière linéaire en $p$. Ce nouvel algorithme nous permet de répondre à une question qui apparaît dans l'étude du modèle d'Ising en physique statistique.
A. Bostan, X. Caruso, É. Schost
A fast algorithm for computing the $p$-curvature
proceedings de la conférence ISSAC 2015

Nous présentons un algorithme pour calculer la $p$-courbure d'un système différentiel en caractéristique $p$. Pour un système de dimension $r$ dont les coefficients ont un degré au plus $d$, la complexité de notre algorithme est $\tilde O (p d r^\omega)$ opérations dans le corps de base (où $\omega$ désigne l'exposant de la multiplication) alors que la taille de la sortie est approximativement $p d r^2$. Notre algorithme est ainsi quasi-optimal si la multiplication matricielle l'est (i.e. si $\omega = 2$). Le principal ingrédient théorique que nous utilisons est l'existence d'un anneau de séries à puissances divisées sur lequel un analogue du théorème de Cauchy–Lipschitz vaut.
A. Bostan, X. Caruso, É. Schost
A fast algorithm for computing the characteristic polynomial of the $p$-curvature
proceedings de la conférence ISSAC 2014

Nous abordons des questions théoriques et algorithmiques en lien avec la $p$-courbure des opérateurs différentiels en caractéristique $p$. Étant donné un tel opérateur $L$ dont le polynôme caractéristique de la $p$-courbure est noté $\chi(L)$, nous démontrons d'abord une formule donnant une description alternative de $\chi(L)$. Celle-ci se trouve être particulièrement adaptée pour un calcul rapide de $\chi(L)$ lorsque $p$ est grand: grâce à elle, nous concevons un nouvel algorithme pour le calcul de $\chi(L)$ dont le coût vis-à-vis de $p$ est $\tilde O(p^{0.5})$ opérations dans le corps de base. Ceci est remarquable car, avant ce travail, les algorithmes les plus rapides connus pour effectuer cette tâche, et même pour décider de la nilpotence de la $p$-courbure, avaient au mieux une complexité sous-quadratique en $\tilde O(p^{1.79})$.
X. Caruso, J. Le Borgne
A new faster algorithm for factoring skew polynomials over finite fields
J. Symbolic Comput. 79 (2017), 411–443

Dans cet article, nous étudions l'arithmétique des anneaux de polynômes tordus sur les corps fini, en ne concentrant principalement sur les aspects algorithmiques. Nous décrivons différents algorithmes pour la multiplication rapide, la division euclidienne et le calcul de pgcd. En utilisant la théorie des algèbres d'Azumaya, nous décrivons certains quotients d'anneaux de polynômes tordus. Enfin, et il s'agit là de notre résultat principal, nous nous basons sur la description suscitée pour concevoir un algorithme rapide de factorisation des polynômes tordus sur les corps finis.

Dernière modification le 12 février 2017