charpoly via Newton

[Pascal Molin <molinp@math.jussieu.fr>]

(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.

Pascal