det en approx
Modérateur : xcasadmin
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
det en approx
Salut,
si je fais:
k:=5;A:=matrix(k,k,(i,j)->rand(21)-10.1);B:=A-X*identity(k)
alors
simplify(det(B))
me donne une fraction.
Et avec k=10 ca ne repond deja plus alors que
time(pari_matdet(B)) met 0.01s
vous aussi?
si je fais:
k:=5;A:=matrix(k,k,(i,j)->rand(21)-10.1);B:=A-X*identity(k)
alors
simplify(det(B))
me donne une fraction.
Et avec k=10 ca ne repond deja plus alors que
time(pari_matdet(B)) met 0.01s
vous aussi?
en effet, ca bloque parce que l'algorithme de Bareiss suppose de simplifier une ligne par le pivot utilisé pour la colonne précédente et avec des coeffs approchés la simplification plante à cause des erreurs d'arrondi. Je change ca pour utiliser l'instruction de quotient euclidien de polynomes au lieu de la division. Ca ne bloquera plus, ca affichera des warnings et ca donne un résultat aberrant.
Tu peux spécifier l'algo souhaité pour la réduction ou le déterminant avec l'option minor_det (pour le déterminant, c'est l'algo de Laplace en temps 2^n, plutot bien adapté s'il y a plusieurs variables symboliques dans la matrice ou si elle est creuse) ou rational_det (qui utilise Gauss tout simple, sans Bareiss).
Sinon, je ne sais pas quel est l'algo utilisé par pari, dans ton cas tu peux bien sur faire pcar(B) (qui recherche le poly minimal et est generiquement en O(n^3)) ou mieux pcar_hessenberg(B) avec l'algo de Hessenberg (egalement en O(n^3) avec des coeffs numériques) qui la est encore plus rapide que l'appel au det generique de pari.
Tu peux spécifier l'algo souhaité pour la réduction ou le déterminant avec l'option minor_det (pour le déterminant, c'est l'algo de Laplace en temps 2^n, plutot bien adapté s'il y a plusieurs variables symboliques dans la matrice ou si elle est creuse) ou rational_det (qui utilise Gauss tout simple, sans Bareiss).
Sinon, je ne sais pas quel est l'algo utilisé par pari, dans ton cas tu peux bien sur faire pcar(B) (qui recherche le poly minimal et est generiquement en O(n^3)) ou mieux pcar_hessenberg(B) avec l'algo de Hessenberg (egalement en O(n^3) avec des coeffs numériques) qui la est encore plus rapide que l'appel au det generique de pari.
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
Merci pour ta reponse,
Oui, dans le livre de Cohen il conseille de faire avec le quotient et de negliger le reste.
D'apres la doc pari_matdet option 0 c'est bareiss, option 1 c'est gauss.
En fait j'ai remarque ce probleme en voulant illustrer que pour le poly caracteristique on pouvait avoir mieux que Bareiss, (ie comparer Faddeev et Bareiss). Mais si je reste en entiers j'ai cru comprendre qu'xcas passait automatiquement par Hessenberg du coup je n'illustrais rien du tout.
Je m'en suis sorti avec pari_matdet(B,0) contre pari_charpoly(A,0) pour comparer via un meme logiciel.
a+
Oui, dans le livre de Cohen il conseille de faire avec le quotient et de negliger le reste.
D'apres la doc pari_matdet option 0 c'est bareiss, option 1 c'est gauss.
En fait j'ai remarque ce probleme en voulant illustrer que pour le poly caracteristique on pouvait avoir mieux que Bareiss, (ie comparer Faddeev et Bareiss). Mais si je reste en entiers j'ai cru comprendre qu'xcas passait automatiquement par Hessenberg du coup je n'illustrais rien du tout.
Je m'en suis sorti avec pari_matdet(B,0) contre pari_charpoly(A,0) pour comparer via un meme logiciel.
a+
Bon, il doit y avoir un bug dans ma doc ou sur ma page agreg. pcar avec 1 seul argument utilise Fadeev sauf si les coefficients sont modulaires. Mais on peut ajouter un second argument à pcar
(la variable x) et un 3ème argument (là ou on veut évaluer le polynome caractéristique). S'il y a 3 arguments, pcar commence par chercher le polynome minimal relatif a un vecteur choisi au hasard (i.e. en cherchant le noyau de la matrice v,A*v,A^2*v, ...,A^n*v). Si ca donne degré n, c'est bon. Sinon ou si pcar a 2 arguments et si A est à coeff entiers exacts, je calcule le det(A-X*Id) pour X=0,..,n (ce qu'on peut faire en modulaire pour de grandes matrices) et je fais une interpolation de Lagrange. Hessenberg n'est utilisé que pour des coefficients dans un corps finis (sauf si tu appelles pcar_hessenberg mais ce n'est pas efficace sur les entiers).
Tout ca est un peu brouillon et mériterait d'etre rationalisé, as-tu des propositions?
par ex. pcar pourrait utiliser par défaut Fadeev, et on pourrait spécifier en dernier argument si on veut utiliser l'algo probabiliste ou l'interpolation de Lagrange.
(la variable x) et un 3ème argument (là ou on veut évaluer le polynome caractéristique). S'il y a 3 arguments, pcar commence par chercher le polynome minimal relatif a un vecteur choisi au hasard (i.e. en cherchant le noyau de la matrice v,A*v,A^2*v, ...,A^n*v). Si ca donne degré n, c'est bon. Sinon ou si pcar a 2 arguments et si A est à coeff entiers exacts, je calcule le det(A-X*Id) pour X=0,..,n (ce qu'on peut faire en modulaire pour de grandes matrices) et je fais une interpolation de Lagrange. Hessenberg n'est utilisé que pour des coefficients dans un corps finis (sauf si tu appelles pcar_hessenberg mais ce n'est pas efficace sur les entiers).
Tout ca est un peu brouillon et mériterait d'etre rationalisé, as-tu des propositions?
par ex. pcar pourrait utiliser par défaut Fadeev, et on pourrait spécifier en dernier argument si on veut utiliser l'algo probabiliste ou l'interpolation de Lagrange.
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
Non, ta doc est OK,
Elle explique bien les algorithmes, par contre je n'ai pas vu de references a ce que faisait pcar, mais je l'ai peut etre loupe.
du coup j'ai fait un grep pcar sur les sources et comme j'ai vu apparaitre hessenberg j'ai conclu trop hativement.
pour la methode par defaut a utiliser je n'ai pas d'idees particulieres, en revanche l'idee d'un argument supplementaire pour preciser la methode est tres bonne, et du coup le ?pcar preciserait tout de suite la methode. Par contre ca me perturbe un peu que pcar(A) et pcar(A,x) ne fassent pas la meme methode, on croit juste que la difference est dans la forme du resultat, mais dans mon exemple pcar(A,x) l'emporte largement, alors que pcar(A) et det(B) sont comparables. (taille 40). Mais bon ca n'a rien de primordial.
En tout cas merci pour tes precisions.
Frederic
Elle explique bien les algorithmes, par contre je n'ai pas vu de references a ce que faisait pcar, mais je l'ai peut etre loupe.
du coup j'ai fait un grep pcar sur les sources et comme j'ai vu apparaitre hessenberg j'ai conclu trop hativement.
pour la methode par defaut a utiliser je n'ai pas d'idees particulieres, en revanche l'idee d'un argument supplementaire pour preciser la methode est tres bonne, et du coup le ?pcar preciserait tout de suite la methode. Par contre ca me perturbe un peu que pcar(A) et pcar(A,x) ne fassent pas la meme methode, on croit juste que la difference est dans la forme du resultat, mais dans mon exemple pcar(A,x) l'emporte largement, alors que pcar(A) et det(B) sont comparables. (taille 40). Mais bon ca n'a rien de primordial.
En tout cas merci pour tes precisions.
Frederic
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
Merci pour les modifs, a premiere vue ca marche maintenant.
plus de Pb en flottants et le options fonctionnent.
En revanche j'ai un decalage d'un dans la doc.
si je fais
?r2e je dois ensuite faire next dans le navigateur pour avoir r2e
J'imagine que c'est juste ma doc qui n'est pas a jour. J'ai pris xcas_root.tgz
A+
Fred
plus de Pb en flottants et le options fonctionnent.
En revanche j'ai un decalage d'un dans la doc.
si je fais
?r2e je dois ensuite faire next dans le navigateur pour avoir r2e
J'imagine que c'est juste ma doc qui n'est pas a jour. J'ai pris xcas_root.tgz
A+
Fred
c'est un probleme de cache des index d'aide HTML. Je vais recreer xcas_root.tgz pour qu'il soit correct. Tu peux faire (avec eventuellement un sudo):
icas --rebuild-help-cache
Sinon, je rajoute une option fadeev pour forcer Fadeev (sauf pour les matrices modulaires pour l'instant) et je remets Lagrange par defaut pour les matrices a coeff entiers.
Je vais essayer aussi de rajouter une option 'mod' (ou 'irem' ou 'ichinrem') pour les operations faisant intervenir la reduction de Gauss pour forcer l'usage d'une methode modulaire. On pourrait alors faire lu(A) ou lu(A,ichinrem) (Bareiss ou modulaire). Il faudra que j'implemente des methodes p-adiques un jour.
icas --rebuild-help-cache
Sinon, je rajoute une option fadeev pour forcer Fadeev (sauf pour les matrices modulaires pour l'instant) et je remets Lagrange par defaut pour les matrices a coeff entiers.
Je vais essayer aussi de rajouter une option 'mod' (ou 'irem' ou 'ichinrem') pour les operations faisant intervenir la reduction de Gauss pour forcer l'usage d'une methode modulaire. On pourrait alors faire lu(A) ou lu(A,ichinrem) (Bareiss ou modulaire). Il faudra que j'implemente des methodes p-adiques un jour.
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
Tres bonne idee, l'option mod.
Pour pcar, j'ai aussi remarque que fadeev marchait moins bien que les autres dans le cas que je testais (coeffs entiers entre -10 et 10). Mais avec pari_charpoly je n'ai pas une difference notable entre fadeev et lagrange. J'ai donc essaye de supprimer la ligne
addvecteur( Ai,multvecteur(pk,I),Bi); // Bi = Ai+pk*I
de vecteur.cc, le resultat est evidemment faux, mais le temps a l'air de chuter beaucoup, alors que normalement cette ligne ne devrait contribuer que pour n^2 additions contre les n^4 multiplicatoins de la methode, non?
a part ca, det_minor a l'air d'avoir un probleme de signe.
seq(det_minor(identity(k)),k=1..15)
me donne parfois des -1
Pour pcar, j'ai aussi remarque que fadeev marchait moins bien que les autres dans le cas que je testais (coeffs entiers entre -10 et 10). Mais avec pari_charpoly je n'ai pas une difference notable entre fadeev et lagrange. J'ai donc essaye de supprimer la ligne
addvecteur( Ai,multvecteur(pk,I),Bi); // Bi = Ai+pk*I
de vecteur.cc, le resultat est evidemment faux, mais le temps a l'air de chuter beaucoup, alors que normalement cette ligne ne devrait contribuer que pour n^2 additions contre les n^4 multiplicatoins de la methode, non?
a part ca, det_minor a l'air d'avoir un probleme de signe.
seq(det_minor(identity(k)),k=1..15)
me donne parfois des -1
Entre fadeev et lagrange, tu as essaye quelles tailles de matrices? Sinon un des avantages de lagrange c'est que je pourrais lancer efficacement des calculs en parallele. Mais par contre je n'ai pas la matrice adjointe.
Sinon pour ta modif dans vecteur.cc, je pense que Ai doit alors avoir des coeffs de taille bien plus petites ce qui fait chuter le temps de calcul.
Il y a bien un bug dans det_minor, je viens de le corriger...merci!
Sinon pour ta modif dans vecteur.cc, je pense que Ai doit alors avoir des coeffs de taille bien plus petites ce qui fait chuter le temps de calcul.
Il y a bien un bug dans det_minor, je viens de le corriger...merci!
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
Oui, c'est vrai que les coefficients deviennent petits.
En taille 30, 40, 50 avec des entiers j'ai un rapport 4 en faveur de lagrange, mais en flottants les 2 sont tres proches.
Sous freeBSD j'ai du mal compiler quelque chose car ton binaire linux (lancé depuis freeBSD) va plus vite pour det et pcar
En taille 30, 40, 50 avec des entiers j'ai un rapport 4 en faveur de lagrange, mais en flottants les 2 sont tres proches.
Sous freeBSD j'ai du mal compiler quelque chose car ton binaire linux (lancé depuis freeBSD) va plus vite pour det et pcar
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :