<\body> <\doc-data|>|> \; <|doc-data|>> \; <|author-data> \; Laboratoire d'Informatique \ École Polytechnique Paris >>> \; <|doc-data||<\author-affiliation> Computer Science Department University of Western Ontario London >>> \; <\em> Deuxième colloque franco-maghrébin de calcul formel Îles de Kerkennah \; 1 octobre 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. \; Relations symétriques :\ <\indent> <\itemize> Définition : k,\,X|]>> tels que \\\,P>,\,\>|)>=0>; Elles forment un idéal \k,\,X|]>> engendré par les ,\,X|)>-f|)>,n>>. \; L' est \k,\,X|]>/\>, son degré est \n!>. \; Pour tout \>, notons son polynôme characté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>>|[, , , 2001]>>| [ , 2000]>>>>>>>||>>>> \; |<\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 characté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 characté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 charactéristique <\equation*> \\\\>>,\,\>|)>|)>. \; |<\hidden> > - Principe> \; Basé sur l' du calcul de résolvantes : <\indent> <\itemize> \T-P,\,X|)>\k,\,X,T|]>> ,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> \; \; :> > \; <\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 charactéristique. |<\hidden> - Formule récursive> \; <\definition*> Soient k> qui s'écrivent ,n>|)>>, ,m>|)>> dans >>. Alors on définit g\k> (resp. g\k>) par <\equation*> |g\i\n, 1\j\m>+\|)>|)>;>>|>|g\i\n, 1\j\m>\\|)>|)>.>>>>> \; <\proposition*> Nous avons la relation <\equation> ,\>=,\>\|)>|)>|\+\*X,\>>>. \; \; <\proposition*> L'algorithme a une complexité quasi-optimale |~>|)>>. \; |<\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> <\with|font-base-size|12> \; \; Résultats théoriques : <\itemize> algorithme efficace pour les calculs dans l'algèbre de décomposition universelle; algorithme efficace pour le calcul de polynôme charactéristique; amélioration de complexité pour le calcul symbolique de résolvantes absolues. \; \; En pratique : <\itemize> Code en cours; algorithme différent pour la représentation à une variable de >. \; |<\hidden> \; \; \; \; \; \; \; \; <\with|par-mode|center> > \; <\with|par-mode|center> <\with|font-base-size|17> > <\initial> <\collection> <\references> <\collection> > > > > > >