Algorithmes détendus pour la multiplication

Algorithmes détendus pour la multiplication

Cette section présente la notion d’algorithmes en-ligne et détendus sur des anneaux p-adiques généraux. Soit R un anneau commutatif avec unité. Étant donné un idéal principal propre (p) avec p ∈ R, nous notons Rp la complétion de l’anneau R pour la valuation p-adique. Les éléments a ∈ Rp sont appelés des p-adiques. Pour avoir l’unicité de la décomposition des éléments de Rp, fixons un sous-ensemble M de R tel que la projection π: M → R/(p) soit une bijection. Alors, tout p-adique a ∈ Rp s’écrit de manière unique a = P i∈N ai p i avec ai ∈ M. Deux exemples classiques sont l’anneau des séries formelles k[[X]] qui est le complété de l’anneau des polynômes k[X] pour l’idéal (X), et l’anneau des entiers p-adiques Zp qui est le complété de l’anneau des entiers Z pour l’idéal (p). Dans le cas, R = Z, nous prendrons M = {−(p − 1)/2, ,(p − 1)/2} si p  2 et M = {0, 1} si p = 2. Pour R = k[X], nous prendrons M = k. Nous sommes maintenant en mesure de donner la définition d’un algorithme détendu telle qu’elle fut introduite par [Hen66]. Définition 1. ([Hen66, FS74]) Soit une machine de Turing qui calcule une fonction f sur des suites, avec f: Σ∗ × Σ ∗ →∆∗ et Σ et ∆ des ensembles. On dit que la machine calcule f en-ligne si, pour toutes suites a = a0a1 an, b= b0b1 bn en entrée et pour des sorties correspondantes f(a, b) = c0c1 cn, avec ai , bj ∈ Σ, ck ∈ ∆, la machine écrit la sortie ck avant de lire soit aj, soit bj, avec 0 6 k < j 6 n. La machine calcule f semi-en-ligne (par rapport au premier argument) si elle écrit la sortie ck avant de lire aj pour 0 6 k < j 6 n. L’entrée a est appelée l’entrée en-ligne et b l’entrée hors-ligne.Le reste de ce chapitre traite des algorithmes en-ligne rapides pour la multiplication de p-adiques. Ces algorithmes sont faits d’appels à des multiplications horsligne de p-adiques de précision finie. Nous rappelons d’abord l’état de l’art des algorithmes de multiplication de polynômes et d’entiers qui sont respectivement les séries formelles et les entiers p-adiques de précision finie. Nous regarderons aussi les algorithmes existants pour les produits court et médian. Avec ces notions à portée de main, nous faisons un rappel des algorithmes détendus suivants de multiplication de p-adiques. Le premier algorithme en-ligne quasi-optimal de multiplication fut présenté dans [FS74] pour les entiers, puis dans [Sch97] pour les nombres réels et finalement dans [Hoe97] pour les séries formelles. Ce dernier algorithme fut adapté en un algorithme semi-détendu (ou semien-ligne) dans [FS74, Hoe03]. Un première amélioration d’un facteur constant du produit semi-détendu est présenté dans [Hoe03]. Notre contribution consiste en la présentation d’un nouvel algorithme détendu utilisant des produits médians et courts qui améliore d’un facteur constant les algorithmes précédents. De plus, nous analysons pour la première fois précisément le nombre de multiplications de base que font ces algorithmes détendus. Pour finir, nous donnons des temps de calcul qui confirment le bon comportement des algorithmes détendus qui utilisent le produit médian. À partir de maintenant, nous utiliserons les notations suivantes. Pour tout padique a= P i∈N ai p i , la longueur λ(a) de a est définie par λ(a)7 1+sup(i∈N|ai  0) si a  0 et λ(0) = 0. Le coût de la multiplication de deux p-adiques de longueur N par un algorithme hors-ligne (resp. en-ligne) est noté I(N) (resp. R(N)) dans notre modèle de complexité précisé en Section 1.1.2. Aussi nous noterons M(N) le nombre d’opérations arithmétiques que nécessite la multiplication de deux polynômes de longueur N. 

Nombres p-adiques récursifs 

L’étude des algorithmes en-ligne est motivée par l’implémentation pratique des padiques récursifs à l’aide de ces algorithmes. Il fut pointé pour la première fois dans [Wat89] que le calcul de séries formelles récursives est bien adapté à l’algorithmique paresseuse. Cela donna lieu à l’époque à un cadre très pratique pour calculer avec les séries formelles récursives, mais pas encore très efficace. Ce fait fut redécouvert par [Hoe02] plus généralement pour l’algorithmique enligne. Mis bout à bout avec l’algorithme en-ligne rapide de multiplication de [Hoe97], van der Hoeven obtint un cadre simple et efficace pour calculer avec les séries formelles récursives. Un p-adique récursif y est un p-adique qui satisfait y = Φ(y) pour un opérateur Φ qui vérifie l’égalité entre les n-ièmes coefficients p-adiques Φ(y)n = Φ(y + a pn )n pour tout a ∈ Rp. Par conséquent, y est uniquement déterminé par la donnée de Φ et de son premier coefficient y0. Dans ce chapitre, nous rappelons la méthode de [Hoe02] qui, à partir d’un algorithme en-ligne qui évalue la fonction Φ, calcule les coefficients du p-adique récursif y l’un après l’autre. Cependant cette méthode ne marche pas toujours tel quel.Notre contribution est d’identifier le problème sous-jacent et de donner une condition suffisante pour que la méthode précédente marche. Nous n’avons pas connaissance de traces de ce problème dans la littérature. Nous introduisons la nouvelle notion d’algorithmes décalés dans l’optique de résoudre ce problème. Un entier, appelé le décalage, est associé à toute entrée padique d’un algorithme donné et mesure quels coefficients de ces entrées sont lus au moment où l’algorithme produit le n-ième coefficient de la sortie. À titre d’exemple, un algorithme est en-ligne si et seulement si son décalage est positif. Finalement un algorithme est un algorithme décalé si son décalage est positif. Nous avons alors à notre disposition les outils nécessaires pour énoncer la proposition fondamentale suivante. Proposition. Soient y un p-adique récursif et Ψ un algorithme décalé tels que y = Ψ(y). Alors le p-adique y peut être calculé à précision N dans le temps nécessaire pour évaluer Ψ en y à précision N. Ainsi, le coût du calcul d’un p-adique récursif est le même que le coût de sa vérification. La proposition précédente est la pierre angulaire des futures estimations de complexité liées à des p-adiques récursifs. Elle sera utilisée dans les chapitres 3, 4, 5 et 6. 

Algèbre linéaire sur les p-adiques

 Dans ce chapitre, nous présentons un algorithme basé sur le cadre détendu pour les p-adiques récursifs du chapitre 2 qui peut en principe être appliqué à n’importe quel choix de représentation de matrices (dense, creuse, structurée, etc.). Nous nous concentrons sur les deux cas particuliers importants que sont les matrices denses et structurées et nous montrons comment notre algorithme peut améliorer les techniques existantes. Considérons un système linéaire de la forme A = B · C, avec A et B connues et C inconnue. La matrice A appartient à Mr×s(Rp) et la matrice B ∈Mr×r(Rp) est inversible ; nous résolvons le système linéaire A = B · C en C ∈Mr×s(Rp). Les cas les plus intéressants sont le cas s = 1, qui revient à résoudre un système linéaire, et s = r, qui contient le problème de l’inversion de B. Une application importante de la résolution linéaire de systèmes à coefficients p-adiques est la résolution de systèmes sur R (c’est-à-dire sur les entiers ou les polynômes par exemple) à l’aide de techniques de remontée. Nous noterons d 7 max (λ(A), λ(B)) la longueur maximale des coefficients des matrices A et B. Soit N la précision à laquelle nous voulons connaître C. Ainsi, nous pourrons toujours supposer que d 6 N. Le cas particulier N = d correspond à la résolution de systèmes linéaires p-adiques en propre, tandis que la résolution de systèmes linéaires sur R nécessite souvent une précision N ≫ d. En effet, dans ce cas et pour les séries formelles par exemple, les formules de Cramer indiquent que les numérateurs et les dénominateurs de C ont une longueur O(r d), de telle sorte que l’on doive prendre N de l’ordre de O(r d) pour permettre la reconstruction rationnelle.