Lazy
Sur une idée de Jean-Louis
Roch, "Lazy" est une nouvelle approche, paresseuse, pour le calcul
avec des nombres algébriques dans le cadre d'une politique de
calcul pour une seule racine.
Référence
:
Logiciels : "Lazy" a
été implémentée dans le module de calcul
avec des nombres algébriques de Givaro, ainsi
qu'avec des routines parallèles de l'environement Athapascan-1.
- Givaro :
une
bibliothèque C++ pour le calcul formel
- Athapascan-1
:
Athapascan-1 is the high level application programming interface of the
parallel environment Athapascan.
Résultats :
 |
Figure 8 : D5 vs approche paresseuse sur un test
d'égalité entre un polynôme de degré
deux cents et un polynôme de degré de
un à dix mille.
|
Extraits de démonstration :
III) Arithmétique des Nombres Algébriques dans un Corps
Dans cette partie, nous rappelons tout d'abord quelques définitions qui
permettent d'introduire les nombres algébriques.
Nous exposons ensuite la méthode D5 de calcul avec des nombres algébriques et
proposons, pour finir, une nouvelle approche de calcul.
A) Définitions
Définition 1 : Soit K un corps de caractéristique quelconque.
Soit P un polynôme à coefficients dans K .
Soit a une racine de P, a est appelé nombre algébrique sur K.
|
Définition 2 : Soit K un corps de caractéristique quelconque.
K est dit algébriquement clos si
¥a nombre algébrique sur K, a  K |
Définition 3 : Soit a un nombre algébrique sur K, défini par P K[X].
On appelle extension algébrique simple de K pour a,
l'ensemble K[a]  (K[X]/P[X], +, ×)
des nombres définis comme polynômes en a. |
Définition 4 : Soit a1 un nombre algébrique sur K, on définit K1=K[a1].
Une tour d'extensions (Ki)i[1..n] est une construction
récursive
telle que K  K1 ... Kn
avec ¥i, Ki=Ki-1[ai]= K[a1,...,ai]. |
Propriété 1 : Soit P K[X] irréductible sur K.
alors (K[X]/P[X], +, ×) a une structure de corps |
L'approche classique utilise la propriété 1 pour définir les opérations de base
et les tours d'extensions. Cependant cela nécessite de factoriser tout polynôme de
définition en ses facteurs irréductibles.
Le système D5 [5] permet de manipuler des nombres algébriques sans avoir
obligatoirement à effectuer la factorisation, toujours très coûteuse (cf. II), des
polynômes Pi, définissant les ai. L'arithmétique pour le calcul entre nombres
algébriques est fondée sur les opérations de base des polynômes (+, -, ×, division
euclidienne) et le calcul du pgcd et des coefficients de Bézout de polynômes.
Enfin on appelle scindage l'action de factoriser ces polynômes lors de calculs.
Les scindages interviennent du fait de la non-irréductibilité des Pi car, ainsi, les
nombres algébriques sont définis sur un ensemble de valeurs possibles.
B) D5 [5]
Le système D5 [5] permet de manipuler des nombres algébriques sans avoir
obligatoirement à effectuer la factorisation, toujours très coûteuse (cf. II), des
polynômes les définissant. L'arithmétique pour le calcul entre nombres algébriques est
fondée sur les opérations de base des polynômes et le calcul du pgcd et des coefficients
de Bézout de polynômes.
En effet, prenons, pour commencer, le cas d'un calcul dans une extension
algébrique simple K[a] avec a, racine d'un polynôme P sur K[X]. Tout nombre
algébrique de K[a] peut alors s'écrire sous la forme d'un polynôme.
Si P n'est pas irréductible, la seule définition de a étant d'être une racine de
P, a peut donc prendre n'importe quelle valeur parmi toutes les racines de P.
Le résultat d'un calcul peut donc être, lui aussi, défini sur un ensemble de
valeurs; toutefois, tant que les opérations du calcul sont des opérateurs arithmétiques
classiques (+, -, ×, division euclidienne), le résultat peut être exprimé sous la forme
d'un nombre algébrique, c'est-à-dire d'un polynôme.
Au contraire, le résultat d'un test d'égalité ne peut s'exprimer comme un
polynôme, c'est seulement “Vrai” ou “Faux”. Il faut diviser les racines de P en deux
sortes, celles pour lesquelles le test vaut “Vrai” et celles pour lesquelles le test vaut
“Faux”; on parle alors de scindage.
La méthode D5 est une méthode pour calculer ces opérations sur une extension
algébrique de K. Soit a nombre algébrique racine de P K[X], et soit N K[X] tel
que notre calcul soit le test N(a) =? 0; D5 procède de la manière suivante :
soit P1 = pgcd(P,N), et P2 = pp(P,P1) (c'est-à-dire que P2 représente les racines
de P qui ne sont pas racines de P1), alors le test N(a) =? 0 est vrai si a est racine de
P1 et faux si a est racine de P2.
Ceci est un scindage de P en P1 et P2.
Il y a alors deux politiques de calcul différentes : on peut choisir de
continuer à calculer pour toutes les racines de P, c'est-à-dire dans K[X]/P1 et dans
K[X]/P2 en parallèle, ou on peut choisir un des deux cas, le calcul n'est alors valable
que pour les racines correspondant au cas choisi et au pire pour une seule racine.
C) Méthode de calcul avec une seule racine : une approche paresseuse
Pour faire un simple test d'égalité par la méthode D5, nous devons effectuer
les calculs assez coûteux d'un pgcd et d'une partie première.
Dans ce paragraphe, nous proposons une nouvelle méthode, dans le cadre de la
politique de calcul pour une seule racine, qui permet de ne pas calculer de pgcd ni de
partie première: l'approche paresseuse.
Avec cette approche, nous conservons, comme définition du nombre algébrique, non
seulement le polynôme de définition P, mais aussi un polynôme N ayant comme racines
communes avec P uniquement celles pour lesquelles nous ne calculons plus.
Théorème : Soit P un polynôme de degré n sur K[X].
Soit C un programme séquentiel comportant h instructions.
Alors, le circuit correspondant à une évaluation de C
dans K[X]/P[X] comporte h.n.log(n) instructions au plus.
Le résultat en sortie est valide pour au moins une des
racines. |
|
Prenons tout d'abord un exemple, toujours le même, a racine de P, nous voulons
tester si N(a)=?0. Nous supposons que P est sans carré (calcul que l'on peut se
permettre une fois, à la définition de a).
Alors : - Si P divise N alors N(a)=0.
- Sinon il existe une racine de P qui n'est pas dans N: on continue les
calculs avec cette racine, on crée la structure paresseuse [P,N] et on répond N(a) != 0.
La structure paresseuse [P,N] signifie que l'on calcule avec a racine de P, et pas de N.
Preuve et Algorithme 1 :
Ainsi on obtient, pour le test d'égalité à zéro auquel il est toujours possible
de se ramener pour tout test d'égalité, l'Algorithme 1 :
Initialisation : [P,1]
Entrées : [P,N] et un polynôme Q.
Sorties : [P,N'] et la réponse au test Q(a) =? 0.
Programme :
1. (quotient,reste) := div(Q×N,P)
2. Si P divise Q×N alors
Retourner [P,N] et Q(a)=0.
Sinon
Retourner [P,reste] et Q(a)!=0. |
En effet, pour le 2., si P divise Q×N toutes les racines de P sont dans Q×N, or nous
travaillons avec une racine de P qui n'est pas dans N, donc elle est forcément dans Q,
d'où la réponse Q(a) = 0. Enfin, si P ne divise pas Q×N alors il existe des racines de P
qui ne sont ni dans N, ni dans Q, nous choisissons de continuer à travailler avec
celles-là. Donc Q(a) != 0. De plus il nous faut conserver ce choix pour les calculs futurs
et donc conserver la structure [P, Q×N], toutefois, le reste de la division contient
toutes les racines de Q×N qui sont également dans P, il est donc suffisant de conserver
[P,reste]. Ainsi nous conservons dans la structure deux polynômes de degré au plus celui
de P et à chaque test il y a au plus une multiplication et deux divisions entre des
polynômes au degré borné.
Enfin, le résultat final est valide pour les racines de P qui ne sont pas dans N,
il en reste au moins une, car N est de degré n-1 (avec n le degré de P).
Il est possible d'obtenir ces racines explicitement mais il faut alors calculer le pgcd de P et N.
Il est facile de généraliser aux tours d'extensions algébriques car dans ce cas,
soit x un nombre algébrique, il existe T K[a1,...,ak-1] tel que x=T(ak).
D'où l'algorithme :
Entrées : {[Pi,Ni]} et un nombre algébrique x.
Sorties : {[Pi,Ni']} et la réponse au test x =? 0.
Programme :
- Si ]k tel que x=T(ak) avec degré(T) > 0
- Si Pk divise T×Nk Retourner [Pk,Nk] et x=0.
- Sinon Retourner [Pk,reste(T×Nk,P)] et x!=0.
- Sinon x K. |
D) Approche paresseuse pour toutes les racines
Algorithme 2 :
Initialisation : [P,1]
Entrées : [P,N] et un polynôme Q.
Sorties : des scindages [Pi,Ni]
et la réponse au test Q(a) =? 0.
Programme :
1. (quotient,reste) := div(Q×N,P)
2. Si P divise Q×N alors
Retourner [P,N] et Q(a) == 0.
Sinon Scinder en
[P,reste] || [pgcd(reste,Q), N×quotient % reste]
Retourner Q(a)!=0. || Retourner Q(a) == 0 |
E) Complexité
Proposition : L'algorithme 1, de test d'égalité dans l'approche paresseuse
a une complexité algébrique parallèle en O(log(d))
et une complexité algébrique séquentielle en O(d2) |
Preuve : Nous avons une multiplication et deux divisions de polynômes de
degrés bornés par d, d'où les complexités sans considérer les
opérations sur le corps de base.