> <\body> <\doc-data|>|> \; <|doc-data|<\doc-author-data|>> \; <|doc-author-data> \; Laboratoire d'Informatique \ École Polytechnique Palaiseau - France >> \; <|doc-data||<\author-address> Computer Science Department University of Western Ontario London - Canada >> \; ALGO seminar, Rocquencourt \; June 11, 2012 |<\doc-note> > \; \; \; \; \; |<\hidden> \; Let be a field of characteristic or sufficiently large. We fix +f*X\k> separable of degree .\ We note ,\,\> its roots. \; \; ||||>||>|,>>=>,\,\>|)> \| \\\|}>>>|>>|=|E,\,X|)>-f|\>,n>\k,\,X|]>>>>>>> \; \; The is \k,\,X|]>/\>, its degree is \n!>. \; \; For all \>, let's denote its characteristic polynomial\ <\equation*> \>\\\>>,\,\>|)>|)>\k. |<\hidden> \; : <\equation*> L\\\//Stab P>>,\,\>|)>|)>\k. We have =|)>>. \; Symbolic methods for the computation of absolute resolvents : <\indent> <\itemize> by resultants \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [], [, '81], [ , '88], [,'97] by symmetric functions \ \ [], [, '88], [, , '94]; by Groebner bases \ \ \ \ \ \ \ \ [ , '88], [, , '93]; by invariants \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [, '29], [, '31]. \; \; > Little is know about complexity. Algorithm with at least quadratic complexity |)>>. |<\hidden> \; <\center> ||||||||||||||||||||||>|>|\k,\,X|]>> >| of a primitive>>|i\n>.>|>. Parametrizations |)>i\n>>.>>||>||||||=k|]>>>|>||)>>>>|>>||>|=k,\,X|]>>>|>|,\,C|)>>>>|>>||>|=\=k,\,X|]>>>|>|,\,C|)>>>>>>>>||||||||||>>|>>|/>>>|>>|>>|>>>|>>|>>|>>>>>>>||>>>> \; Cost of the representation of >: \ |||||||||||||||)>> by the recursive formula :>||~>|)>> \ \ \ \ \ \ \ by FGLM or RUR algorithm>>|| et al., '93], [, '99]>>||>|=,\,X|)>-C,\,X|)>|)>|X-X>>>>||||~>|)>> \ \ \ \ \ \ \ by geometric resolution >>| , '01], [ , '00]>>>>>>>|\f|)>>.>|>|||~>|)>> \ \ \ \ by modular composition \ \ \ >>||, '11]>>>>> \; |<\hidden> \; <\center> ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||>|\k,\,X|]>> >| of a primitive>>|i\n>.>|>. Parametrizations |)>i\n>>.>>||>||||||=k|]>>>|>||)>>>>|>>||>|=k,\,X|]>>>|>|,\,C|)>>>>|>>||>|=\=k,\,X|]>>>|>|,\,C|)>>>>>>>>||||||||||>>|>>|/>>>|>>|>>|>>>|>>|>>|>>>>>>>||>>>> \; Cost of arithmetic operations in >: \ |||||||||||||||||||||||||||||||>||~>|)>> [ et , 2011],>||~>|)>>, simple and efficient>>| not implemented, significant constant>|>||>||>|no quasi-optimal algorithm>||~>|)>>, simple and efficient>>||>||>>>> |<\hidden> Let =\\k,\,X|]>> and =!>> its degree. \; <\theorem*> One can compute a primitive linear form \\> and the univariate representation =,\,S|)>\k|]>> with <\equation*> ||=k,\,X|]>/\>|>||]>/Q|)>>>|>|>||)>>>|>|>|>>>>>> with a Las Vegas algorithm of expected cost +1|)>/2>*m*\|)>|)>>>. \; <\theorem*> For all \>, the characteristic polynomial >\k> costs <\equation*> \+1|)>/2>*m*\|)>|)> arithmetic operations in . |<\hidden> \; \; <\itemize> Computation of > <\itemize> > Symbolic computation of absolute Lagrange's resolvent in time |~>|)>>; \; \; Computation of \k/Q>\ <\itemize-dot> > Change of representation in time |~>|)>> > Division in > in time |~>|)>> > Efficient algorithms for trace, minimal polynomial computations... > Dynamic splitting field, [ , 1985] > Effective invariant theory \; \; \; |<\hidden> \; <\indent*> <\enumerate-roman> Computation of >> for a linear form \\> Change of representation : Up and Down Univariate representation of > Benchmarks \; <\enumerate-roman> <\indent> Computation of > for any \> Benchmarks Generalizations \; |<\hidden> <\definition*> Let k> monic and ,\,\> all its root in a suitable extension. Then the -th of is <\equation*> S\=1>>|)>\k. The of is |)>i\n>>. \; <\proposition*> The conversion from and to the Newton representation can be done in time |)>>. \; <\lemma*> Multiplication in the Newton representation: <\equation*> S=S+S. |<\hidden> <\definition*> Let k> such that ,r>|)>>, ,s>|)>> in >>. Then <\equation*> |g\i\r, 1\j\s>+\|)>|)>\k>>|>|g\i\r, 1\j\s>\\|)>|)> \ \ \ \ \ \ \k>>>>> \; <\proposition*> If n,>then g> and g> can be computed in time |)>|)>>. <\proof> One has <\equation*> Sg|)>=S*S and <\equation*> \>g|)>|i!>T=\>|i!>T|)>*\>|i!>T|)>. \; \; \; |<\hidden> \; Let =\*X+\+\*X\\>, compute <\indent> <\equation*> \>\\\>*\>+\+\*\>|)>|)>. \; \; <\itemize> |)>=*\|)>=\*X,\>> If =,\,\|}>>, then <\eqnarray*> f>||,\\R>+\|)>|)>>>|||\\\R>+\|)>|)>*\R>|)>>>|||+X,\>\\,\>>>>> \ |<\hidden> \; Formula from [, , '94]: <\equation*> \+\+X>=+\+X>|)>\|)>|)>> \; <\proposition*> <\indent> <\itemize-dot> One has <\equation> ,\>=,\>\|)>|)>|\+\*X,\>>>, where =\*X+\+\*X\\>. The associated recursive algorithm computes ,\>> in time *\|)>|)>>. \; Algorithm in the Newton representation, handle multiplicities, memoization Factor > |<\hidden> \; <\indent> <\itemize> minimal polynomial : =\>>; parametrizations : <\lemma*> Let k,\,T|]>> and \T*X+\+T*X\K,\,X|]>>. Then >\k,\,T|]>> and <\equation*> X*=-\>|\T>|)>/\>|\T>|)>\. \; <\indent> In practice, we use tangent numbers k|]>/|)>> to compute derivatives : <\itemize-minus> If >\+\|)>*X+\*X+\+\*X> then >>=\>+\*\>|\T>>. \; |<\hidden> <\indent> <\itemize> minimal polynomial : =\>>; parametrizations : <\lemma*> Let k,\,T|]>> and \T*X+\+T*X\K,\,X|]>>. Then >\k,\,T|]>> and <\equation*> X*=-\>|\T>|)>/\>|\T>|)>\. \; <\proposition*> Suppose given a primitive linear form \\> and an algorithm to compute >> in time >.Then a parametrization > can be computed in time |)>>. \; <\corollary*> A univariate representation =,S,\,S|)>> of > costs *m*\|)>|)>>. > \; \; \; |<\hidden> \; <\indent*> <\enumerate-roman> Computation of >> for a linear form \\> Univariate representation of > Benchmarks \; <\enumerate-roman> <\indent> Computation of > for any \> Benchmarks Generalizations \; |<\hidden> \; Compute efficiently \ \ =k,\,X|]>/,\,C|)>\k|]>/|)>|)>> \ \ and >. \; \; <\equation*> |||]>/|)>>|>|>>||>||>>| : >|,X|]>/|)>,C,X|)>|)>>|>||]>/|)>>>>>>. \; \; <\indent> <\equation*> Up: \ \ \=|]>/C|)>,X|]>/,C|)>\> |]>/Q|)>|]>/|)>\> k|]>/|)> with , =X>. \; |<\hidden> \; Compute efficiently \ \ =k,\,X|]>/,\,C|)>\k|]>/|)>|)>> \ \ and >. \; \; <\equation*> |||||,X|]>/|)>,C,X|)>|)>>|>||]>/|)>>>| :>|>|>|-\*S|)>>>||>|>||)>>>>>>. \; \; >:>> <\indent> Input: \ k,X|]>> Ouput: \>|]>/|)>> <\enumerate> Compute ,X|)>=P-\*X,X|)>\|]>/f|)>|)>|]>>\|)>> Substitute \S|)>> in ,X|)>>|)>> \; |<\hidden> \; Compute efficiently \ \k|]>/|)>|)>> and its converse map >. \; <\proposition*> \; <\enumerate> Given ,Q> and >, we can apply > in time *\|)>|)>>. Given ,S|)>i\n>>, we can apply in time *n*\|)>|)>>. \; \; <\indent> <\equation*> Up: \ \ \ \=|]>/C|)>,X|]>/,C|)>\> |]>/Q|)>|]>/|)>\> k|]>/|)> with , =X>. |<\hidden> >> > <\indent> <\itemize> k> a primitive linear form \X+\*X+\+\*X> of > <\indent> <\itemize> a univariate representation =,S,\,S|)>> of >. \; <\itemize> Use to get for i\n>: <\itemize> |||>>| \ \*\|)>|)>>>>>>>\ |||> of >>| \ \*\|)>|)>>>>>>> Get the other parametrizations: |)>=Up|)>> \ \*n*\|)>|)>> \; \; |<\hidden> \; - Good timings: ||||||||||||||>>||||||>| |<\cell> \; |<\cell> 4 |<\cell> 5 |<\cell> 6 |<\cell> 7 |<\cell> 8 >|||>|>|||6h>>||>|||>|>|>>>>> with 2.17-1 over > with prime number of bits.\ \; \; - Complexity of not quasi-optimal: *\|)>|)>>. - does not compute > for general \>. |<\hidden> \; <\indent*> <\enumerate-roman> Computation of >> for a linear form \\> Change of representation : Up and Down Univariate representation of > Benchmarks \; <\enumerate-roman> <\indent> Computation of > for any \> Benchmarks Generalizations \; |<\hidden> > for any \>> \; Based on the to compute resolvents: <\indent> <\itemize> \T-P,\,X|)>\k,\,X,T|]>> i=n-1,\,0,R\Res>,R|)>\k,\,X,T|]>> =R\k>. \; \; Mathematically, <\equation*> Res> :\|]>\\|]>\\. \; \; Multiplication in > in time |~>|)>> + resultant algorithm on general ring <\indent> > Computation of > for any \> in time |~>|)>> > Not practical \; |<\hidden> > for any \>> > \> >> \; <\enumerate-numeric> |||\Up>>|\|]>/Q|)>|]>>>>>>> for 1> do <\indent> \Up|)>>\|]>/Q|)>|]>> \Res>,G|)>>\|]>/Q|)>> \down|)>>\|]>/Q|)>|]>> |||\down|)>>>|\k>>>>>> \; Cost of : +1|)>/2>*n*\|)>|)>> |<\hidden> > for any \>> > <\indent> <\itemize> k>; a primitive linear form \X+\*X+\+\*X> of >; <\indent> <\itemize> a univariate representation =,S,\,S|)>> of >. \; \; <\itemize> For i\n>, use to get : <\itemize> the minimal polynomials >+1|)>/2>*n*\|)>|)>>\ the last parametrizations > of >+1|)>/2>*n*\|)>|)>> Get the other parametrizations: |)>=Up|)>>*n*\|)>|)>> \; |<\hidden> > \; 2.17-1 over > with prime number of bits. \; ||||||||||||||\>>>||||||>| |<\cell> \; |<\cell> 4 |<\cell> 5 |<\cell> 6 |<\cell> 7 |<\cell> 8 >||/Q> [,'99]*>|>|>|>|>|>>||*>|||||>>>> \; \; \; ||||||||||||||||||\> linear>>||||||>| |<\cell> \; |<\cell> 4 |<\cell> 5 |<\cell> 6 |<\cell> 7 |>||>||||>|>>||/Q> [,'99]*>|>|>|>||>||*>|||||>>>> (*) Requires the precomputation of a univariate representation\ \; \; |<\hidden> > \; 2.17-1 on one core of a Intel Xeon @2.27GHz, 74Gb of RAM over > with prime number of bits. \; \; |||||||||||<\cell> 5 |<\cell> 6 ||>||||||>||||||>||> *>|s>>|>||>||> *>||||>|| triangular >>||||>|| triangular >>|||30 >|6 >>>>> \; (*) Requires the precomputation of a univariate representation\ \; \; \; \; |<\hidden> \; <\indent*> <\enumerate-roman> Computation of >> for a linear form \\> Change of representation : Up and Down Univariate representation of > Benchmarks \; <\enumerate-roman> <\indent> Computation of > for any \> Benchmarks \; |<\hidden> \; Adapt the situation to \>. \; <\equation*> \=k,\,X|]> \\\G,R>,\,\>|)>=0|}> \; <\remark*> If >, then ,\,X|]>/\> is a decomposition field of . \; <\itemize> , '03] [, '04] [, , '06 '08] [, '09] \; \; \; |<\hidden> \; <\itemize> Resultant approach is general and still in good complexity, due to i,f|)>=0> \; \; <\itemize> Computation of relative resolvents <\equation*> L\\G//Stab P>>,\,\>|)>|)>\k, where k,\,X|]>>. \; Faster arithmetics in decomposition fields \; |<\hidden> \; \; <\itemize> first quasi-linear algorithm for univariate representation in >; first quasi-linear algorithm for characteristic polynomial in >; Complexity improvement for the symbolic computation of absolute resolvents. \; \; <\itemize> code; better timings for univariate representation of >, Up, Down; as a result, better timings for arithmetic operations in >, characteristic polynomial... \; |<\hidden> \; \; \; \; \; \; <\with|par-mode|center> > \; <\with|par-mode|center> <\with|font-base-size|17> > <\initial> <\collection> <\references> <\collection> > > > > > >