Une matrice est appelée matrice creuse si de nombreux coefficient sont nuls.
On considère des matrices carrées à \(n\) lignes et \(n\) colonnes. Le nombre de coefficients est donc \(n^2\). Dans une matrice creuse le nombre de coefficients non nuls est de l'ordre de \(n\).
Cette matrice est représentée en Python par: m = [[0, 1, 0, 0, 0], [1, -1, 0, 0, 0], [0, 0, 2, 0, 0], [0, 0, -2, 1, 0], [0, 0, 0, 0, 3]]
Plutôt que de stocker toute la matrice, soit \(n^2\) coefficients, on utilise trois tableaux pour ne stocker que les coefficients non nuls de la matrice qui est parcourue ligne par ligne. On note \(n\) le nombre de lignes et \(nb\) le nombre
de coefficients non nuls. Les trois tableaux sont définis ainsi:
un tableau valeurs de taille \(nb\) qui contient les \(nb\) coefficients non nuls;
un tableau colonnes de taille \(nb\) qui contient les indices des colonnes des coefficients non nuls (colonnes[k] est l'indice de la colonne contenant valeurs[k]);
un tableau lignes de taille \(n+1\) tels que lignes[0] vaut 0, pour \(0 < k < n\), lignes[k] est l'indice dans le tableau valeurs du premier coefficient non nul de la ligne \(k\) ou bien lignes[k-1] si tous les coefficients de la ligne \(k\) sont nuls, lignes[n] est le nombre de coefficients non nuls.
Ainsi, lignes[k+1] - lignes[k] est le nombre de coefficients non nuls de la ligne \(k\).
Par exemple, avec la matrice m, \(n = 5\), \(nb=7\), on obtient les trois tableaux valeurs, colonnes, lignes:
[1, 1, -1, 2, -2, 1, 3], les coefficients non nuls rencontrés suivant l'ordre ligne par ligne, colonne par colonne;
[1, 0, 1, 2, 2, 3, 4], les indices des colonnes auxquelles appartiennent les coefficients non nuls;
[0, 1, 3, 4, 6, 7], \(1-0\) est le nombre de coefficients non nuls de la ligne d'indice \(0\), \(3-1\) est le nombre de coefficients non nuls de la ligne d'indice \(1\),
\(4-3\) est le nombre de coefficients non nuls de la ligne d'indice \(2\), \(6-4\) est le nombre de coefficients non nuls de la ligne d'indice \(3\),
\(7-6\) est le nombre de coefficients non nuls de la ligne d'indice \(4\), $7 est le nombre total de coefficients non nuls.
Cette représentation consomme moins d'espace en mémoire. On rencontre des matrices creuses en particulier dans la résolution de systèmes linéaires.
C'est aussi le cas avec la matrice d'adjacence d'un graphe comportant peu d'arêtes.
Question 1
Écrire la fonction stockage qui prend en paramètre une matrice, représentée par une liste de listes comme ci-dessus et renvoie les trois tableaux valeurs, colonnes, lignes.
Pour cela commencer par parcourir la matrice ligne par ligne, colonne par colonne, pour compter le nombre d'éléments non nuls. Créer ensuite les trois tableaux
aux bonnes dimensions, initialement remplis de 0. Parcourir à nouveau la matrice, et à chaque coefficient non nul rencontré, modifier en conséquence les tableaux.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Le produit d'une matrice carrée \(m\) notée \((m_{i j})\) à \(n\) lignes et \(n\) colonnes par un vecteur \(x\) noté \((x_i)\) de taille \(n\) est un vecteur \(y\) noté \((y_i)\) de taille \(n\) tel que
pour tout \(i\) de 1 à \(n\), \(y_i = \sum_{k=1}^{n} m_{i k} x_k\)
Avec une matrice creuse, pour obtenir la valeur de \(y_i\), on n'utilise que les coefficients non nuls de la ligne \(i\).
Question 2
Écrire la fonction produit qui prend en paramètres les trois tableaux représentant une matrice creuse m et un tableau représentant le vecteur x
et qui renvoie le vecteur y, produit de m par x.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)