restart;maple_mode(0);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); //radians,pas de cmplx, pas de Sqrt // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 -------------------------Determinant----------------------------------------------- // fltk N4xcas23Comment_Multiline_InputE 20 599 916 71 12 Sur un corps fini comme avec des flottants on peut modeliser le cout desŁ operations par des constantes c+,c*,c/ ... Dans ce modele le pivot de GaussŁ est en O(n^3) operations sur le corps (il faut n^2 transvections) alors que laŁ methode de Laplace avec les % mineurs est en 2C^2_n+3C^3_n+4C^4_n+.... n:=10; M:=ranm(n,n)%101; time(d1:=det(M,rational_det)); time(d2:=det(M,minor_det)); d1-d2; n:=15; M:=ranm(n,n)%101; time(d1:=det(M,rational_det)); time(d2:=det(M,minor_det)); purge(n,k);// Le nombre de multiplications par Laplace: O(n.2^n) somme(k*binomial(n,k),k=0..n); // fltk N4xcas23Comment_Multiline_InputE 20 599 916 86 12 Sur Z et Q le pivot traditionnel perd beaucoup de temps car les fractions sontŁde plus en plus lourdes a calculer. On n'est pas dans un modele a coutŁconstant. La methode de Bareiss qui reste dans Z est donc tresŁavantageuse. Celle par defaut est une methode modulaire. (pivot dans Z/pZ puisŁl'on remonte) n:=50;M:=smod(ranm(n,n,20)); time(d1:=det(M,rational_det)); time(d2:=det(M,bareiss)); time(d3:=det(M)); // fltk N4xcas23Comment_Multiline_InputE 20 599 916 42 12 attention, le == n'est pas une instruction mathematique. Cela ne vaut vrai queŁ si les expressions sont identiques. Ex: a+b==b+a retourne 0. d1==d2;d2==d3; purge(a); n:=4;A:=matrix(n,n,(u,v)->a[u,v]); d3:=det(A,rational_det); time(normal(d3));time(simplify(d3));time(expand(d3)); // fltk N4xcas23Comment_Multiline_InputE 20 599 916 57 12 La facon la plus rapide de developper avec simplifications rationnelles estŁtoujours normal. Pour etre coherent il faut developper det(A,rational_det) pourŁle comparer aux autres. time(d3:=normal(det(A,rational_det))); time(d4:=(det(A,bareiss))); time(d5:=(det(A,minor_det))); d3==d4;d4==d5; // fltk N4xcas23Comment_Multiline_InputE 20 599 916 71 12 Avec beaucoup de variables formelles, on se retrouve tres vite avec des taillesŁou l'on ne peut plus rien calculer par aucune methodes. Un peu avant la methodeŁpar les mineurs tire souvent son epingle du jeu, et d'autant plus si la matriceŁest creuse. (avec pas mal de 0). n:=6;A:=matrix(n,n,(u,v)->a[u,v]); time(d3:=normal(det(A,rational_det))); time(d4:=(det(A,bareiss))); time(d5:=(det(A,minor_det))); d3==d4;d4==d5; // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 -------------------------Polynome minimal----------------------------------------------- v:=[seq(ii,ii=1..8)]; poly2symb(v,x); revlist(v); P:=x^2+1;LP:=[1,0,1]; subst(P,x=sqrt(2)); unapply(P,x)(sqrt(2));//c'est preferable et plus Ex pour creer une fonction peval(LP,sqrt(2)); n:=8:;v:=[seq(ii,ii=1..n)]; A:=matrix(n,n,(i0,j0)-> rand(20)-10); B:=v; AA:=v; // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 eviter cette syntaxe maple en mode xcas: for ii from 1 to n do AA:=A*AA;B:=B,AA; od; for(ii:=1;ii<=n;ii++){ AA:=A*AA;B:=B,AA;} N:=nullspace(transpose([B]))[0]; // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 Attention, les polyn\^omes commencent a la puissance maximale, il faut inverser l'ordre P:=poly2symb(revlist(N),x); normal(subst(P,x=A)); A:=diag(companion(x^4-1,x),companion((x^2-1)^2,x)); B:=v; AA:=v // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 eviter cette syntaxe maple en mode xcas: for ii from 1 to n do AA:=A*AA;B:=B,AA; od; for(ii:=1;ii<=n;ii++){ AA:=A*AA;B:=B,AA;} nullspace(B); N:=nullspace(transpose([B]))[0]; P:=poly2symb(revlist(N),x); normal(subst(P,x=A)); // fltk N4xcas23Comment_Multiline_InputE 20 599 916 42 12 On a calcul\'e les A^k(v) par recurence. AA est un vecteur donc A*AA a un cout deŁn^2, et l'on fait n tours, donc c'est en O(n^3) // fltk N4xcas23Comment_Multiline_InputE 20 599 916 42 12 Il existe toujours un vecteur v tel que P_(u,v)=pmin(u), les vecteurs a eviterŁ sont dans ker(P(u)) ou P divise pmin, donc nom fini despace vectoriels a eviter. // fltk 7Fl_Tile 27 324 909 188 12 [ // fltk N4xcas7EditeurE 27 324 909 187 12 285 , minval(A):={ local m,u,v,ii,j; m:=0;u:=-1;v:=-1; // NB: On retourne -1,-1 si A est nulle for( ii:=0; ii0) and ((m=0) or (abs(A[ii,j])[-1,-1]) and size(B)>1){ // attention, ne pas oublier de declarer les variables locales // dans trans pour eviter les melanges B:=trans(B,ii,j); if ([ii,j]==[minval(B)]){ // on n'a que des zeros sur la ligne i et la colonne j sauf // en (i,j) on sauve donc B[i,j] et on raye ligne et colonne. k:=k+1; l[k]:=B[ii,j]; B:=delcols(B,j..j); B:=delrows(B,ii..ii); //le cas B de taille 1 pose probleme car on ne peut pas rayer //une colonne puis une ligne } // ASTUCE: voici comment assigner 2 valeurs d'un coup. (ii,j):=minval(B); } // On a eventuellement change le signe du determinant diag([seq(l[k],k=0..n-2),B[0,0]]); }; A:=matrix([[2,2,2],[6,12,6],[6,4,6]]); //Exemple: Zequiv(A); A[3,3]:=12:;A; Zequiv(A); // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 On v\'erifie que A et Zequiv(A) ont bien meme forme de smith: ismith(A)[1], ismith(Zequiv(A))[1]; // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 Attention, on n'obtient pas forcement les diviseurs elementaires, par exemple: A:=matrix([[4,0,0],[0,6,0],[0,0,8]]); ismith(A)[1]; Zequiv(A);