|
Matrice sparsa In matematica, in particolare in analisi numerica, una matrice sparsa è una matrice i cui valori sono quasi tutti uguali a zero. Concettualmente, la sparsità si collega ai sistemi accoppiati. Si consideri una serie di palline in cui ognuna di esse è collegata alla successiva tramite delle molle; questo è un sistema sparso. Di contro, se le stesse palline fossero state tutte collegate l'una all'altra, il sistema sarebbe stato rappresentato da una matrice densa. Il concetto di sparsità è utile nel calcolo combinatorio e in quelle aree di applicazione, quali la teoria delle reti, in cui vi sia una bassa densità di dati o di relazioni significative. Matrici sparse di una certa complessità appaiono spesso in alcune discipline scientifiche od ingegneristiche quando è necessario risolvere equazioni differenziali alle derivate parziali. Quando delle matrici sparse vengono memorizzate e gestite su un computer, risulta proficuo, e spesso anche una necessità, utilizzare algoritmi specializzati e strutture dati che tengono conto della natura sparsa della matrice. Svolgere delle operazioni utilizzando le strutture e gli algoritmi matriciali usuali risulta un'operazione molto lenta, e porta anche a grandi sprechi di memoria, se la matrice da gestire è sparsa. I dati sparsi sono, per loro natura, facilmente comprimibili, e la loro compressione comporta quasi sempre un utilizzo significativamente inferiore di memoria. È pur vero, però, che alcune matrici sparse molto estese sono impossibili da gestire con gli algoritmi standard. Memorizzazione di una matrice sparsaLa struttura dati classica di una matrice è quella di un array bidimensionale. Ogni elemento dell'array rappresenta il generico elemento ai,j, a cui si può avere accesso tramite i due indici i e j. Per una matrice m×n dev'essere disponibile almeno il minimo quantitativo di memoria necessario ad immagazzinare gli (m×n) valori della matrice. Molti, se non tutti, i valori di una matrice sparsa sono pari a zero. Il principio di base che si segue per memorizzare una matrice sparsa è di salvare, invece di tutti i valori, soltanto quelli diversi da zero. A seconda del numero e della distribuzione dei valori diversi da zero, si possono utilizzare diverse strutture dati ed ottenere risparmi considerevoli in termini di memoria impossibili da ottenere con l'approccio usuale. Un esempio di un formato per memorizzare matrici sparse è il (vecchio) Yale Sparse Matrix Format, che memorizza una matrice sparsa m×n, M, in una riga usando tre array monodimensionali. Sia Ad esempio, la matrice [ 1 2 0 0 ] [ 0 3 9 0 ] [ 0 1 4 0 ] è una matrice tre per quattro con sei elementi diversi da zero, per cui A = [ 1 2 3 9 1 4 ] IA = [ 1 3 5 7 ] JA = [ 1 2 2 3 2 3 ] Un'altra possibilità è usare dei quadtree. EsempioUn'immagine bitmap bicromatica, in cui uno dei due colori è predominante (si pensi ad un file che memorizza una firma scritta a mano) può essere codificato come una matrice sparsa che contiene solo i numeri di righe e di colonne dei pixel con il colore non dominante. Matrici diagonaliUna struttura di matrice diagonale molto efficiente prevede la memorizzazione dei soli valori della diagonale principale come array monodimensionale, così che una matrice diagonale n×n richiede soltanto n valori. BandaLa banda inferiore di una matrice A è il più piccolo numero p tale che il valore aij sia trascurabile quando i > j + p. Similmente, la banda superiore è il più piccolo p tale che aij = 0 quando i < j − p (Golu, Van Loan, 1996 §1.2.1). Ad esempio, una matrice tridiagonale ha banda inferiore e banda superiore pari ad 1. Matrici con banda inferiore e superiore piccola sono note come matrici a banda e spesso si prestano ad algoritmi più semplici di quelli applicabili alle matrici sparse in genere; a volte è possibile applicare algoritmi per matrici dense e ripeterne l'uso su un numero di indici ridotto. Riduzione della bandaSi può usare l'algoritmo Cuthill-McKee per ridurre la banda di una matrice simmetrica sparsa. Vi sono, tuttavia, matrici per cui l'algoritmo Cuthill-McKee inverso si comporta meglio. L'U.S. National Geodetic Survey (NGS) usa l'algoritmo cosiddetto "del Bancario" di Richard Snay perché è più rapido nell'operare su matrici sparse realistiche usate in Geodesia. Si possono usare altri metodi. Ridurre il fill-inIl fill-in di una matrice è costituito da quei valori che da zero diventano diversi da zero durante l'esecuzione di un algoritmo. Per ridurre i requisiti di memoria e il numero di operazioni aritmetiche utilizzate in un algoritmo, è utile minimizzare il fill-in scambiando righe e colonne della matrice. La decomposizione simbolica di Cholesky può essere utilizzata per calcolare il fill-in peggiore possibile prima di svolgere la vera e propria decomposizione di Cholesky. Altri metodi diversi dalla decomposizione di Cholesky possono essere utilizzati. Metodi di ortogonalizzazione (come la fattorizzazione QR) sono comuni, ad esempio, nella risoluzione di problemi con il metodo dei minimi quadrati. Sebbene il fill-in sia in teoria il medesimo, in termini pratici i "falsi valori diversi da zero" possono essere diversi se i metodi cambiano. Le versioni simboliche di questi algoritmi possono essere usati in maniera simile a Cholesky simbolico per calcolare il caso peggiore di fill-in. Risoluzione di sistemi di equazioni associate a matrici sparseEsistono sia metodi iterativi, sia diretti per la risoluzione di sistemi associati a matrici sparse. Un metodo iterativo molto comune è quello del gradiente coniugato. BibliografiaFonti
Approfondimenti
Voci correlate
Altri progetti
|
