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