> <\body> \; <\doc-data|>|> \; <|doc-data|<\doc-author-data|>> \; <|doc-author-data> \; Laboratoire d'Informatique \ École Polytechnique Palaiseau >> \; <|doc-data||<\author-address> Computer Science Department University of Western Ontario London >> \; <\em> Journées Nationales du Calcul Formel Luminy \; 16 novembre 2011 |<\doc-note> > \; \; \; \; \; \; |<\hidden> \; Fixons un corps effectif de caractéristique ou suffisamment grande. Fixons +f*X\k> séparable de degré .\ Notons ,\,\\>> ses racines. \; Définitions : ||||||>|=|E,\,X|)>-f|\>,n>\k,\,X|]>>>|>>|,>>=>,\,\>|)> \| \\\|}>>>>>>> \; \; L' est \k,\,X|]>/\>, son degré est \n!>. \; Pour tout \>, notons son polynôme caractéristique\ <\equation*> \>\\\>>,\,\>|)>|)>\k. \; |<\hidden> \; : <\equation*> L\\\//Stab P>>,\,\>|)>|)>\k. On a la relation =|)>>. \; \; Méthodes symboliques pour le calcul de résolvantes absolues : <\indent> <\itemize> par les résultants \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [], [, 1981], [ , 1988], [,1997]; par les fonctions symétriques [], [, 1988], [, , 1994]; par les bases standards \ \ \ \ \ \ \ [ , 1988], [, , 1993]; par des invariants \ \ \ \ \ \ \ \ \ \ \ \ \ \ [, 1929], [, 1931]. \; \; > Pas d'étude de complexité. Algorithmes non optimaux en |)>>. |<\hidden> \; <\center> |||||||||||||||||||||||>|\k,\,X|]>> \ >| d'une forme linéaire>>|i\n>.>|>. Paramétrisations |)>i\n>>.>>||>||||||=k|]>>>|>||)>>>>|>>||>|=k,\,X|]>>>|>|,\,MC|)>>>>|>>||>|=\=k,\,X|]>>>|>|,\,MC|)>>>>>>>>||||||||||||>>|>>|/>>>|>>|>>|>>>|>>|>>|>>>>>>>||>>>> \; \; Coût du calcul de la représentation : \ ||||||||||||)>> par la formule récursive :>||~>>|)>> par l'algorithme de base de Gröbner F4>>|| [, 1999]>>||>|>\,\,X|)>-MC,\,X|)>|)>|X-X>>>||~>|)>> par l'algorithme de résolution géométrique>>||[ , '01], [ , '00]>>|\f|)>>.>|>|||~>+1|)>/2>|)>> par composition modulaire>>|| [, 2011]>>>>> \; |<\hidden> \; <\center> ||||||||||||||||||>|\k,\,X|]>> \ >| d'une forme linéaire>>|i\n>.>|>. Paramétrisations |)>i\n>>.>>||>||||||=k|]>>>|>||)>>>>|>>||>|=k,\,X|]>>>|>|,\,MC|)>>>>|>>||>|=\=k,\,X|]>>>|>|,\,MC|)>>>>>>>>||||||||||||>>|>>|/>>>|>>|>>|>>>|>>|>>|>>>>>>>||>>>> \; \; Coût des opérations de base : \ ||||||||||||||||||||||||||||||||>||~>|)>> [ et , 2011],>||~>|)>>, simple et efficace>>| MAIS non implémenté, grande constante>|>||>||>|pas d'algorithme quasi-optimal>||~>|)>>, simple et efficace>>||>||>||>>>> |<\hidden> \; <\theorem*> Pour tout \>, le polynôme caractéristique \k> peut être calculé en <\equation*> \*|)>|)>=|~>|)> opérations arithmétiques dans . \; <\theorem*> Supposons donnée une forme linéaire primitive >. Alors une représentation à une variable =,Q,S,\,S|)>\k,\,X|]>\k> où <\equation*> ||=k,\,X|]>/\>|>|/Q>>|>|>|>>|,\,X|)>>|>|>>>>> se calcule en complexité arithmétique *|)>|)>=|~>|)>>>. \; <\remark> L'article [, , ] nous permet de rendre le choix de > déterministe non-uniforme. |<\hidden> \; \; <\itemize> Calcul du polynôme caractéristique > <\itemize> > Calcul symbolique de résolvantes de Lagrange absolues en complexité |~>|)>> \; \; Calcul d'une représentation \k/Q> à une variable <\itemize-dot> > Algorithmes pour les opérations arithmétiques en |~>|)>> opérations dans . > Algorithmes efficaces pour le calcul de trace, polynôme minimum... > Corps de décomposition dynamique, [ , 1985] > Calcul d'une représentation de l'idéal galoisien alterné, [, 2010] \; |<\hidden> \; \; :> > \; Entrée :\ <\indent> <\itemize> un polynôme k>; un polynôme k,\,X|]>> réduit; pour tout i\n>, une représentation à une variable =,Q,S,\,S|)>> de \\\k,\,X|]>> tel que\ <\equation> \i\,n|}>,\\\k,\=\+\*X. \; Sortie :\ <\indent> <\itemize> le polynôme caractéristique <\equation*> \\\\>>,\,\>|)>|)>. \; |<\hidden> > - Principe> \; Basé sur l' du calcul de résolvantes : <\indent> <\itemize> \T-P,\,X|)>\k,\,X,T|]>> i=n-1,\,0,R\Res>,R|)>\k,\,X,T|]>> =R\k>. \; \; Mathématiquement, <\equation*> Res> :\|]>\\|]>\\. Algorithmiquement, <\equation*> Res> :|]>/Q|)>|]>\|]>/Q|)>|]>\|]>/Q|)>. \; <\lemma*> Chaque calcul de résultant coûte |~>|)>> opérations arithmétiques dans . |<\hidden> > - Changement de représentation> \; Rappel : <\indent> <\itemize> =Res>,R|)>> \\> > :\|]>\\|]>\\> \; Changement de représentation : <\equation*> ||||>|>||]>/|)>>>||>||>>| :>||]>/|)>>|>|,X|]>/|)>,Q|)>>>||>|>|+\*X>>>>>. \; <\lemma*> Le calcul de |)>> se fait en complexité |~>|)>>. <\proposition*> L'algorithme > \ a une complexité arithmétique quasi-optimale |~>|)>>. |<\hidden> \; \; :> > \; \; Entrée :\ <\indent> <\itemize> les représentations à une variable > de \\\k,\,X|]>> pour tout i\n>. \; Sortie :\ <\indent> <\itemize> le polynôme caractéristique <\equation*> \\\\>>,\,\>|)>|)>. \; Complexité : |~>|)>>. |<\hidden> \; \; :> > \; <\indent> <\itemize> un polynôme k>; une forme linéaire primitive > de >; pour tout i\j-1>, une représentation à une variable =,Q,S,\,S|)>> de > tel que\ <\equation> \i\,j-1|}>,\\\k,\=\+\*X. \; <\indent> <\itemize> une représentation à une variable =,Q,S,\,S|)>> de >. \; |<\hidden> - Calcul d'une représentation à une variable> \; <\indent> <\itemize> polynôme minimal : =\>>; paramétrisations : <\lemma*> Si k,\,T|]>> et \T*X+\+T*X\K,\,X|]>>. Ainsi >\k,\,T|]>> et\ <\equation*> X*\>|\T>+\>|\T>=0\. \; <\indent> En pratique, on utilise les nombres tangents k|]>/|)>> pour calculer les dérivées. \; \; <\proposition*> Étant donné un élément primitif \\>, le coût du calcul d'une représentation à une variable de > est |)>> où > est le coût d'un polynôme caractéristique. |<\hidden> - Formule récursive> <\definition*> Soient k> qui s'écrivent <\equation*> f=,n>|)>, g=,m>|)> dans >>. Alors on définit <\equation*> |g\i\n, 1\j\m>+\|)>|)>\k;>>|>|g\i\n, 1\j\m>\\|)>|)>\k.>>>>> \; <\proposition*> Nous avons la relation <\equation> ,\>=,\>\|)>|)>|\+\*X,\>>>. \; <\proposition*> L'algorithme a une complexité quasi-optimale |~>|)>>. <\proof> Utiliser l'algo > dans la formule récursive. |<\hidden> \; :> > \; <\indent> <\itemize> un polynôme k>; une forme linéaire primitive \X+\*X+\+\*X> de >; \; <\indent> <\itemize> une représentation à une variable =,Q,S,\,S|)>> de >. \; <\itemize> <\itemize> Représentation =,f,T|)>> de >; <\indent> \>+\*X+\+\*X,\|)>> > \; > Complexité |~>|)>> |<\hidden> > \; \; La théorie :\ <\itemize-dot> algorithmique quasi-optimale pour >. \; \; En pratique : <\itemize> Algorithme \S Sommes de Newton \T pour la représentation \k/Q> :\ <\itemize-minus> formule récursive : >=>\|)>|)>|\+\*X> >>>; > calcul de *X+\+\*X>> en |~>*\|)>>; > \ calcul de la représentation \k/Q> en |~>*\|)>>. \; Algorithme \S Calcul de Traces \T pour le polynôme caractéristique de k/Q> en +1|)>/2>|)>> [, 99]. \; |<\hidden> > \; 2.17-1 sur un Intel Xeon 16 c÷urs à 2.27GHz, 74Gb de RAM. Sur un corps fini > avec premier de bits.\ \; |||||||||||||>||||||>| |<\cell> \; |<\cell> 4 |<\cell> 5 |<\cell> 6 |<\cell> 7 |<\cell> 8 >|||||||4h>>|||||||>>>> \; \; Précalcul d'une représentation à une variable (*) |||||||||||||\> générique>>||||||>| |<\cell> \; |<\cell> 4 |<\cell> 5 |<\cell> 6 |<\cell> 7 |<\cell> 8 >||]*>|||||>|||||||>>>> \; ||||||||||||||*X+\+\*X\\>>>||||||>| |<\cell> \; |<\cell> 4 |<\cell> 5 |<\cell> 6 |<\cell> 7 |>||]*>|||||>|||||||>|||||||>>>> \; \; \; \; \; \; \; \; |<\hidden> \; \; \; \; \; \; \; \; <\with|par-mode|center> > \; <\with|par-mode|center> <\with|font-base-size|17> > <\initial> <\collection> <\references> <\collection> > > > > > >