Matriu dispersa

Exemple de matriu dispersa" $\left({\begin{smallmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{smallmatrix}}\right)$

Una matriu dispersa obtinguda en resoldre un problema d'elements finits en dues dimensions. Els elements diferents de zero es mostren en negre.

En l'anàlisi numèrica i la computació científica, una matriu dispersa o matriu escassa és una matriu en què la majoria dels elements són zero. No hi ha una definició estricta sobre la proporció d'elements de valor zero perquè una matriu es qualifica com a escassa, però un criteri comú és que el nombre d'elements diferents de zero és aproximadament igual al nombre de files o columnes. Per contra, si la majoria dels elements són diferents de zero, la matriu es considera densa. El nombre d'elements de valor zero dividit pel nombre total d'elements (per exemple, m × n per a una matriu m × n) de vegades es coneix com l'esparsitat de la matriu.

Conceptualment, l'escassetat correspon a sistemes amb poques interaccions per parelles. Per exemple, considereu una línia de boles connectades per molles d'una a l'altra: aquest és un sistema escàs ja que només s'acoblen boles adjacents. Per contra, si la mateixa línia de boles tingués molles que connectessin cada bola amb totes les altres boles, el sistema correspondria a una matriu densa. El concepte de dispersió és útil en combinatòria i àrees d'aplicació com la teoria de xarxes i l'anàlisi numèrica, que normalment tenen una baixa densitat de dades o connexions significatives. Sovint apareixen matrius grans disperses en aplicacions científiques o d'enginyeria quan es resolen equacions en derivades parcials.

Quan s'emmagatzemen i manipulen matrius disperses en un ordinador, és beneficiós i sovint necessari utilitzar algorismes especialitzats i estructures de dades que aprofitin l'estructura escassa de la matriu. S'han fet ordinadors especialitzats per a matrius escasses, ja que són habituals en el camp de l'aprenentatge automàtic. Les operacions que utilitzen estructures i algorismes estàndard de matriu densa són lentes i ineficients quan s'apliquen a matrius disperses grans, ja que el processament i la memòria es malgasten en els zeros. Les dades escasses per naturalesa es comprimeixen més fàcilment i, per tant, requereixen molt menys emmagatzematge. Algunes matrius disperses molt grans no són factibles de manipular mitjançant algorismes estàndard de matriu densa.

Existeixen mètodes iteratius i directes per a la resolució de matrius disperses. Els mètodes iteratius, com el mètode del gradient conjugat.