Une propriété structurelle d'une représentation discrète (typiquement une matrice ou un tenseur) où la plupart des entrées sont exactement nulles ou négligeablement petites, permettant des formats de stockage et des algorithmes spécialisés exploitant le motif des non-nuls.

Principe

Les opérateurs discrets issus d'interactions locales (éléments finis à support compact, stencils locaux) produisent des matrices avec des motifs de non-nuls limités ; exploiter la sparsité réduit la mémoire et la complexité de calcul en évitant les opérations sur les zéros et en se concentrant sur le graphe des non-nuls.

Démonstration

La matrice de raideur d'une discrétisation par éléments finis d'une EDP elliptique d'ordre deux est creuse : chaque ligne contient des non-nuls seulement pour les degrés de liberté des éléments voisins, et le stockage CSR creux avec solveurs creux directs ou itératifs réduit fortement le coût par rapport à un traitement dense.

Mauvaise application

Considérer une matrice comme creuse alors que de nombreuses petites entrées, globalement importantes, ont été nullifiées par seuillage, provoquant une déficience de rang ou une perte de conservation ; ou utiliser des formats creux naïfs pour des matrices à structure de blocs denses, entraînant de mauvaises performances.

Conséquence

L'exploitation correcte de la sparsité permet un stockage et des performances de solveur en temps linéaire (ou quasi-linéaire) pour de nombreux problèmes à grande échelle, permet des préconditionneurs évolutifs et des réordonnancements basés sur le graphe, et est centrale pour la simulation à grande échelle.

Inversion

Densité : une représentation où la plupart des entrées sont non nulles, nécessitant un stockage et des algorithmes denses ; un comportement dense peut apparaître après factorisation (fill-in) même si la matrice d'origine était creuse.

Limite

La sparsité concerne le motif des entrées numériques proches de zéro dans les représentations discrètes et exclut les stratégies de compression complémentaires (bas rang, hiérarchique ou aléatoire) qui réduisent la complexité en partant d'hypothèses structurelles différentes.

Tension sémantique

La sparsité est en tension conceptuelle avec la compressibilité (approximations de bas rang) : les deux réduisent la charge de calcul mais exploitent des structures différentes — la sparsité utilise des zéros explicites et le couplage local, la compressibilité exploite des corrélations globales.

Synthèse

La sparsité est la présence majoritaire de zéros dans les opérateurs discrets, résultant de la structure locale de la discrétisation ; reconnaître et préserver le motif des non-nuls oriente les formats de stockage, le choix des solveurs et l'évolutivité algorithmique.