Re: charpoly via Newton

[Xavier Francois Roblot <roblot@math.univ-lyon1.fr>]

On Oct 24, 2012, at 1:01 PM, Pascal Molin <molinp@math.jussieu.fr> wrote:

> (sorry for writing in french)
> 
> En écrivant des sujets de tp, je découvre que calculer un polynôme
> caractéristique par les sommes de Newton n'est pas déraisonnable,
> en tous cas avec pari pour des matrices en caractéristique moyenne (0
> ou >dimension dans la fonction ci-dessous):
> 
> charpoly_newton(A) = {
>  my(d = matsize(A)[1]);
>  my(B = matid(d));
>  my(S = x*Ser(vector(d,i,B*=A;-trace(B)/i)));
>  polrecip(Pol(exp(S)));
> };
> 
> [gp-2.6 sur paridev] ============
> ? A = matrix(100,100,i,j,random(Mod(1,1009)));
> ? charpoly(A);
> time = 2,329 ms.
> ? charpoly_newton(A);
> time = 408 ms.
> ===========================
> 
> L'algo peut être généralisé/amélioré (évaluation des traces avec BSGS,
> extension aux caractéristiques p<dim) : dites-moi
> si ça peut être intéressant.
> 
> Dans tous les cas, je souhaiterais proposer pour Pari un certain
> nombre d'opérations sur les polynômes (reconstruction à partir
> des sommes de Newton, produits composés, puissances symétriques --
> c'est initialement ça que je voulais --...), modalités et
> syntaxe à voir par exemple durant l'atelier de janvier.

The main task in the FPR-Round 4 algorithm for the computation of the maximal order of a number field is the computations of the characteristic polynomials of elements in some étale extension of Qp. Upon the advice of H. Cohen, it is implemented using Newton sums (using some caching). Anything that could improve this part of the computation would lead to a significant speed-up of this part of the code. I think it is therefore definitely worth exploring. 

Best,

Xavier