determinants

Message par **parisse** » mer. sept. 24, 2008 12:46 pm

Je suis en train d'essayer d'optimiser le calcul de determinants a coeffs polynomiaux. On peut dorenavant specifier l'algo en 2nd argument:
- det(A,minor_det): developpement (intelligent) des mineurs
- det(A,lagrange): interpolation
- det(A,bareiss): Bareiss
si l'algo n'est pas specifie, giac choisit entre Lagrange et Bareiss en fonction de la majoration du degre total et des degres partiels (j'espere que le choix est judicieux mais je n'en suis pas sur...). Je n'ai pas encore ajoute de detection des matrices creuses ou le developpement des mineurs est plus rapide.
Pour les determinants a coeffs entiers, l'algorithme determine (presque surement) le plus grand facteur invariant de la matrice par calcul p-adique d'une solution du systeme, puis reconstruit le quotient determinant/facteur invariant par evaluation mod p et restes chinois. Il s'arrete avant la borne de Hadamard si le resultat reste constant pour suffisamment de nombres premiers, l'algorithme est donc probabiliste, on controle la probabilite d'erreur dans la fenetre de configuration de xcas (valeur du champ proba).

frederic han · Message par **frederic han** » mer. sept. 24, 2008 8:19 pm

oula ca marche bien!!

En entiers pour un poly caracteristique (sans options ou lagrange) j'ai l'impression que ca vaut pcar mais aussi pari_charpoly!

Seule l'option bareiss est plus longue que pari_matdet (qui d'apres la doc fait aussi cette methode.)

NB: si les coeff sont des poly a coeff flottants l'option lagrange plante.

Message par **parisse** » jeu. sept. 25, 2008 7:59 am

je pense avoir corrige, ca plantait quand le polynome etaient simplifies (par calcul du pgcd de chaque ligne), par exemple sur det(evalf(idn(2)*(1-x)),lagrange)

frederic han · Message par **frederic han** » jeu. sept. 25, 2008 9:33 am

Ok,

det devient plus rapide que resultant!
pour des polynomes comme ca ou
P:=poly2symb([seq(rand(10)*x+rand(10)*z-rand(5),i=1..k)],y)

comme ca
P:=poly2symb([seq(rand(10)*x^2+rand(10)*x-rand(5),i=1..k)],y)

et Det mod marche bien aussi

En revanche
Resultant n'a pas l'air de vouloir le troisieme argument ie la variable, donc je n'ai pas pu comparer en modulaire.

Message par **parisse** » jeu. sept. 25, 2008 11:48 am

oui, il faut que je rajoute aussi la possibilite de faire un resultant mod avec la syntaxe maple.
Et aussi que j'ajoute de l'interpolation ailleurs (resultant, bezout, pgcd quand le modulaire ne marche pas...).

frederic han · Message par **frederic han** » jeu. sept. 25, 2008 7:53 pm

NB:
Resultant mod existe deja, mais il n'accepte que 2 arguments (ie c'est forcement par rapport a x) alors que
resultant(P,Q,y) fonctionne, mais pas la forme inerte:
'resultant(P,Q,y)' mod 2

Message par **parisse** » ven. sept. 26, 2008 5:53 am

frederic han a écrit :NB:
Resultant mod existe deja, mais il n'accepte que 2 arguments (ie c'est forcement par rapport a x) alors que
resultant(P,Q,y) fonctionne, mais pas la forme inerte:
'resultant(P,Q,y)' mod 2

Salut!
Sous cette forme ca ne marchera pas parce que P et Q ne sont pas evalues, je viens de corriger la forme
Resultant(P,Q,y) mod 2
(dans xcas_unstable.tgz)
a+