Discussion :

[chiheb205]

bonjour
je suis en train de faire un td sur le matrice creuse,je pas bien compris le principe,sous weekpedia j ai trouvé un exemple qui explique ca
il ya un matrice [ 1 2 0 0 ]
[ 0 3 9 0 ]
[ 0 1 4 0 ]

aprés il ya une representation de cet matrice
A = [ 1 2 3 9 1 4 ]
IA = [ 1 3 5 7 ]
JA = [ 1 2 2 3 2 3 ]

avec
Le premier tableau est noté A et est de longueur NNN. Il contient toutes les valeurs des entrées non nulles de M de gauche à droite et de haut en bas (les valeurs sont prises de gauche à droite sur la première ligne, puis de gauche à droite sur la deuxième et ainsi de suite)
Le deuxième tableau est noté IA de longueur m + 1 (le nombre de lignes plus un). L'élément i de IA contient l'index dans le tableau A de la première entrée non nulle de la ligne i de la matrice M. La ligne i de la matrice originale est composée des éléments de A depuis l'index IA(i) jusqu'à l'index IA(i+1)-1.
Le troisième tableau est noté JA de longueur NNN contient le numéro de la colonne de chaque élément de A
Par exemple, la matrice 3×4 suivante



j ai compris le A et le Ja mais je pas compris le IA

merci de m avoir m expliqué ca

[diogene]

Si la première entrée (la plus à gauche) non nulle de la Iieme ligne est placée en position K dans A, alors IA(I) = K. De plus IA(N+1) est défini comme l'indice dans A ou JA de la position du dernier élément de la dernière ligne +1

On peut construire IA de la façon suivante :
IA(1) = 1
IA(I+1) = IA(I)+ Nombre d'élémements non nuls de la ligne I

Le nombre d'entrées de la ligne I est alors IA(I+1)-IA(I)
La première entrée de la ligne I est située dans A et JA à la position : IA(I)

Exemple 1 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1 0 2 0 0 
0 3 0 0 0 
0 4 5 6 0
0 0 0 7 0
0 0 0 8 9

A  1 2 3 4 5 6 7 8 9
JA 1 3 2 2 3 4 4 4 5
IA 1 3 4 7 8 10

Reconstitution Ligne 1 
Nombre d'entrées : IA(2)-IA(1) = 3-1 = 2
Début : IA(1) = 1
JA(1)= 1 : A(1) = 1 est en colonne 1  : 1 0 0 0 0
JA(2)= 3 : A(2) = 2 est en colonne 3  : 1 0 2 0 0

Reconstitution Ligne 2
Nombre d'entrées : IA(3)-IA(2) = 4-3 = 1
Début : IA(2) = 3
JA(3)= 2 : A(3) = 3 est en colonne 2  : 0 3 0 0 0

Reconstitution Ligne 3 
Nombre d'entrées : IA(4)-IA(3) = 7-4 = 3
Début : IA(3) = 4
JA(4)= 2 : A(4) = 4 est en colonne 2  : 0 4 0 0 0
JA(5)= 3 : A(5) = 5 est en colonne 3  : 0 4 5 0 0
JA(6)= 4 : A(6) = 6 est en colonne 4  : 0 4 5 6 0
....

Exemple 2 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
0 0 0 0 0
1 0 2 0 0 
0 0 0 0 0 
0 4 5 6 0


A  1 2 4 5 6 
JA 1 3 2 3 4
IA 1 1 3 3 6

Reconstitution Ligne 1                
Nombre d'entrées : IA(2)-IA(1) = 1-1 = 0
                                      : 0 0 0 0 0
Reconstitution Ligne 2  
Nombre d'entrées : IA(3)-IA(2) = 3-1 = 2
Début : IA(2) = 1
JA(1)= 1 : A(1) = 1 est en colonne 1  : 1 0 0 0 0
JA(2)= 3 : A(2) = 2 est en colonne 3  : 1 0 2 0 0

Reconstitution Ligne 3                
Nombre d'entrées : IA(4)-IA(3) = 3-3 = 0
                                      : 0 0 0 0 0
Reconstitution Ligne 4  
Nombre d'entrées : IA(5)-IA(4) = 6-3 = 3
Début : IA(4) = 3
JA(3)= 2 : A(3) = 4 est en colonne 2  : 0 4 0 0 0
JA(4)= 3 : A(4) = 5 est en colonne 3  : 0 4 5 0 0
JA(5)= 4 : A(5) = 6 est en colonne 4  : 0 4 5 6 0

Sur cette question, voir ici (article en anglais)