[Scilab]Remplacement de sous-matrice sparse
Résolu
cuicuicuilesptitsoiseaux
Messages postés
152
Statut
Membre
-
cuicuicuilesptitsoiseaux Messages postés 152 Statut Membre -
cuicuicuilesptitsoiseaux Messages postés 152 Statut Membre -
Bonjour,
j'ai un problème avec un programme scilab (et matlab aussi) : j'ai une matrice
creuse, nommée globale, très grande. Et à un moment, je dois remplacer des sous-matrices
de globale par d'autres, ce que je fais de la manière suivante :
globale(num_donn,num_pas_donn) = spzeros(length(num_donn),length(num_pas_donn));
globale(num_pas_donn,num_donn) = spzeros(length(num_pas_donn),length(num_donn));
globale(num_donn,num_donn) = d;
num_donn et num_pas_donn sont des vecteurs d'indices, d une matrice diagonale...
Mon problème est que ça réorganise complétement la manière dont est codée la matrice en creux, ce qui prend
beaucoup de temps !
J'aimerai savoir si quelqu'un a une idée pour faire autrement, et surtout plus vite.
Merci !
j'ai un problème avec un programme scilab (et matlab aussi) : j'ai une matrice
creuse, nommée globale, très grande. Et à un moment, je dois remplacer des sous-matrices
de globale par d'autres, ce que je fais de la manière suivante :
globale(num_donn,num_pas_donn) = spzeros(length(num_donn),length(num_pas_donn));
globale(num_pas_donn,num_donn) = spzeros(length(num_pas_donn),length(num_donn));
globale(num_donn,num_donn) = d;
num_donn et num_pas_donn sont des vecteurs d'indices, d une matrice diagonale...
Mon problème est que ça réorganise complétement la manière dont est codée la matrice en creux, ce qui prend
beaucoup de temps !
J'aimerai savoir si quelqu'un a une idée pour faire autrement, et surtout plus vite.
Merci !
A voir également:
- [Scilab]Remplacement de sous-matrice sparse
- Remplacement coco - Accueil - Réseaux sociaux
- Coco.fr remplacement - Accueil - Réseaux sociaux
- Scilab - Télécharger - Édition & Programmation
- Vivastreet rencontre remplacement ✓ - Forum Réseaux sociaux
- Coco chat remplacement ✓ - Forum Réseaux sociaux
2 réponses
je ne comprend pas trop ta question, peux tu expliquer ce qui te pose problème dans l'exemple ci-dessous :
-->A=sparse(eye(10,10));//une matrice creuse
-->full(A)//affichage de A en matrice "pleine"
ans =
1. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 1. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 1. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 1. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 1. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 1. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 1. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 1. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 1. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 1.
-->B=sparse(2*ones(5,5));//un block à insérer dans A
-->full(B)
ans =
2. 2. 2. 2. 2.
2. 2. 2. 2. 2.
2. 2. 2. 2. 2.
2. 2. 2. 2. 2.
2. 2. 2. 2. 2.
-->A(1:5,6:10)=B;//insertion du block en haut à droite de A
-->full(A)//pour contrôle
ans =
1. 0. 0. 0. 0. 2. 2. 2. 2. 2.
0. 1. 0. 0. 0. 2. 2. 2. 2. 2.
0. 0. 1. 0. 0. 2. 2. 2. 2. 2.
0. 0. 0. 1. 0. 2. 2. 2. 2. 2.
0. 0. 0. 0. 1. 2. 2. 2. 2. 2.
0. 0. 0. 0. 0. 1. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 1. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 1. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 1. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 1.
-->sparse(A)//c'est quoi le problème de réorganisation de A?
ans =
( 10, 10) sparse matrix
( 1, 1) 1.
( 1, 6) 2.
( 1, 7) 2.
( 1, 8) 2.
( 1, 9) 2.
( 1, 10) 2.
( 2, 2) 1.
( 2, 6) 2.
( 2, 7) 2.
( 2, 8) 2.
( 2, 9) 2.
( 2, 10) 2.
( 3, 3) 1.
( 3, 6) 2.
( 3, 7) 2.
( 3, 8) 2.
( 3, 9) 2.
( 3, 10) 2.
( 4, 4) 1.
( 4, 6) 2.
( 4, 7) 2.
( 4, 8) 2.
( 4, 9) 2.
( 4, 10) 2.
( 5, 5) 1.
( 5, 6) 2.
( 5, 7) 2.
( 5, 8) 2.
( 5, 9) 2.
( 5, 10) 2.
( 6, 6) 1.
( 7, 7) 1.
( 8, 8) 1.
( 9, 9) 1.
( 10, 10) 1.
avec A de taille 1000x1000 et B de taille 500x500 ça marche aussi très bien (et très vite).
Philippe.
-->A=sparse(eye(10,10));//une matrice creuse
-->full(A)//affichage de A en matrice "pleine"
ans =
1. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 1. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 1. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 1. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 1. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 1. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 1. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 1. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 1. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 1.
-->B=sparse(2*ones(5,5));//un block à insérer dans A
-->full(B)
ans =
2. 2. 2. 2. 2.
2. 2. 2. 2. 2.
2. 2. 2. 2. 2.
2. 2. 2. 2. 2.
2. 2. 2. 2. 2.
-->A(1:5,6:10)=B;//insertion du block en haut à droite de A
-->full(A)//pour contrôle
ans =
1. 0. 0. 0. 0. 2. 2. 2. 2. 2.
0. 1. 0. 0. 0. 2. 2. 2. 2. 2.
0. 0. 1. 0. 0. 2. 2. 2. 2. 2.
0. 0. 0. 1. 0. 2. 2. 2. 2. 2.
0. 0. 0. 0. 1. 2. 2. 2. 2. 2.
0. 0. 0. 0. 0. 1. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 1. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 1. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 1. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 1.
-->sparse(A)//c'est quoi le problème de réorganisation de A?
ans =
( 10, 10) sparse matrix
( 1, 1) 1.
( 1, 6) 2.
( 1, 7) 2.
( 1, 8) 2.
( 1, 9) 2.
( 1, 10) 2.
( 2, 2) 1.
( 2, 6) 2.
( 2, 7) 2.
( 2, 8) 2.
( 2, 9) 2.
( 2, 10) 2.
( 3, 3) 1.
( 3, 6) 2.
( 3, 7) 2.
( 3, 8) 2.
( 3, 9) 2.
( 3, 10) 2.
( 4, 4) 1.
( 4, 6) 2.
( 4, 7) 2.
( 4, 8) 2.
( 4, 9) 2.
( 4, 10) 2.
( 5, 5) 1.
( 5, 6) 2.
( 5, 7) 2.
( 5, 8) 2.
( 5, 9) 2.
( 5, 10) 2.
( 6, 6) 1.
( 7, 7) 1.
( 8, 8) 1.
( 9, 9) 1.
( 10, 10) 1.
avec A de taille 1000x1000 et B de taille 500x500 ça marche aussi très bien (et très vite).
Philippe.
L'intérêt des matrices creuses c'est d'économiser de la mémoire mais bien sûr ça à un coup : le temps de calcul. Trouver la place d'un élément dans une matrice creuse prend un temps au pire proportionnel au nombre d'éléments (n) dans la matrice creuse (au pire il faut passer en revue toutes les positions). Comme tu dois faire ça pour chaque élément (m en tout) du bloc à insérer le temps de calcul total doit être de l'ordre m*n. A partir de là le temps que tu donnes pour des matrices de tailles 50000*50000 me semble tout à fait "raisonnable" comparé à ce que j'obtiens par extrapolation à partir du temps de calcul pour des matrices plus petites.
Désolé mais je n'ai pas de solution pour ton problème,
Philippe.
Désolé mais je n'ai pas de solution pour ton problème,
Philippe.
Bon, pour ceux que ça intéresse :
1) voilà comment finalement on peut gagner du temps pour ce genre de calcul :
[ligne,col,v] = find(globale);
vrai = ones(length(v),1);
h = 1;
while((h<length(num_donn)+1))
temp = ((ligne(:)-num_donn(h)*ones(length(v),1)).*...
(col(:)-num_donn(h)*ones(length(v),1)) ~= zeros(size(ligne(:)-num_donn(h)*ones(length(v),1))));
vrai = vrai.*temp;
h = h + 1;
end
temp = find(vrai);
%ijprime = [ij(temp,:);[num_donn',num_donn']];
vprime = [v(temp);d*ones(length(num_donn),1)];
ligneprime = [ligne(temp);num_donn'];
colprime = [col(temp);num_donn'];
globale = sparse(ligneprime,colprime,vprime);
ici c'est en synthaxe matlab, mais pour scilab il suffit d'adapter. Aussi bizarre que ça puisse paraître, je gagne vraiment du temps en faisant comme ça ! (le truc c'est que num_donn contient "peu" d'éléments, donc la boucle est vite faite)
2) Je me suis rendu compte que la première méthode marche TRÈS BIEN avec OCTAVE ! Elle doit être implémentée autrement que scilab et matlab.
Voilà. À plus !
1) voilà comment finalement on peut gagner du temps pour ce genre de calcul :
[ligne,col,v] = find(globale);
vrai = ones(length(v),1);
h = 1;
while((h<length(num_donn)+1))
temp = ((ligne(:)-num_donn(h)*ones(length(v),1)).*...
(col(:)-num_donn(h)*ones(length(v),1)) ~= zeros(size(ligne(:)-num_donn(h)*ones(length(v),1))));
vrai = vrai.*temp;
h = h + 1;
end
temp = find(vrai);
%ijprime = [ij(temp,:);[num_donn',num_donn']];
vprime = [v(temp);d*ones(length(num_donn),1)];
ligneprime = [ligne(temp);num_donn'];
colprime = [col(temp);num_donn'];
globale = sparse(ligneprime,colprime,vprime);
ici c'est en synthaxe matlab, mais pour scilab il suffit d'adapter. Aussi bizarre que ça puisse paraître, je gagne vraiment du temps en faisant comme ça ! (le truc c'est que num_donn contient "peu" d'éléments, donc la boucle est vite faite)
2) Je me suis rendu compte que la première méthode marche TRÈS BIEN avec OCTAVE ! Elle doit être implémentée autrement que scilab et matlab.
Voilà. À plus !
le problème que j'évoque n'apparaît pas dans ton exemple : il faut des matrices beaucoup beaucoup plus grande
(des matrices 50000*50000 par exemple). Le problème vient du stockage creux : si tu demandes d'insérer un élément
en plein milieu de la matrice (ou pire au début), il est obligé
1) de trouver dans la structure creuse où il doit le mettre
2) de décaler tous les éléments après celui-ci dans ses vecteurs codant sa matrice
Ce processus prend pas mal de temps pour un élément (comparé au temps mis pour faire la même chose pour une matrice pleine), mais quand tu changes une partie entière de la matrice en
1 seul coup, c'est pire (par exemple pour moi les 3 lignes citées dans le message d'avant prennent de l'ordre de 2 min).