Matrice sparsa

Da Wikipedia, l'enciclopedia libera.

Una matrice sparsa ottenuta approssimando una funzione in due dimensioni con il metodo degli elementi finiti. I valori diversi da zero sono rappresentati in nero.

Nell'ambito matematico dell'analisi numerica una matrice sparsa è una matrice i cui valori sono quasi tutti pari 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 specifializzati 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, pero, che alcune matrici sparse molto estese sono impossibili da gestire con gli algoritmi standard.

[modifica] Memorizzazione di una matrice sparsa

La struttura dati classica di un matrice è quella di un array bidimensionale. Ogni elemento dell'array rappresenta il generico elemento a_i,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 sparsi 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 NNZ il numero di valori diversi da zero di M. Il primo array è A, di lunghezza NNZ/, e memorizza tutti i valori diversi da zero di M, ordinati da sinistra a destra e dal basso verso l'alto. Il secondo array è IA, che è lungo m (ossia un valore per riga). IA(i) contiene l'indice del primo elemento di A diverso da zero della riga i-sima. La lunghezza della riga i è determinata da IA(i+1) - IA(i), per cui IA dev'essere di lunghezza m + 1. Il terzo array, JA, contiene l'indice della colonna di ciascun elemento di A, quindi JA è lunga NNZ.

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.

[modifica] Esempio

Un'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.

[modifica] Matrici diagonali

Una 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.

[modifica] Banda

La banda inferiore di una matrice A è il più piccolo numero p tale che il valore a_ij sia trascurabile quando i > j + p. Similmente, la banda superiore è il più piccolo p tale che a_ij = 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.

[modifica] Riduzione della banda

Si 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.

[modifica] Ridurre il fill-in

Il 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.

[modifica] Risoluzione di sistemi di equazioni associate a matrici sparse

Esistono sia metodi iterativi, sia diretti per la risoluzione di sistemi associati a matrici sparse. Un metodo iterativo molto comune è quello del gradiente coniugato.

[modifica] Argomenti correlati

• Rappresentazione matriciale
• Principio di Pareto
• Matrice irregolare
• Array sparso
• Codice di grafo sparso
• File sparso

[modifica] Fonti

• (EN) Tewarson, Reginald P, Sparse Matrices (Part of the Mathematics in Science & Engineering series), Academic Press Inc., May 1973. (Questo libro, scritto da un professore dell'Università Statale di New York a Stony Book, è stato il primo libro interamente dedicato alle matrici sparse. Corsi di laurea che lo usavano come libro di testo si sono tenuti nei primi anni Ottanta).
• (EN) Sparse Matrix Multiplication Package, Randolph E. Bank, Craig C. Douglas [1]
• (EN) Pissanetzky, Sergio 1984, "Sparse Matrix Technology", Academic Press
• (EN) R. A. Snay. Reducing the profile of sparse symmetric matrices. Bulletin Géodésique, 50:341–352, 1976. Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.

[modifica] Per approfondire

• (EN) Norman E. Gibbs, William G. Poole, Jr. and Paul K. Stockmeyer (1976). A comparison of several bandwidth and profile reduction algorithms. ACM Transactions on Mathematical Software 2 (4): 322–330.
• (EN) John R. Gilbert, Cleve Moler and Robert Schreiber (1992). Sparse matrices in MATLAB: Design and Implementation. SIAM Journal on Matrix Analysis and Applications 13 (1): 333–356.
• (EN) Gene H. Golub; Charles F. Van Loan. Matrix Computations. 3^a ed. Baltimora, Johns Hopkins, 1996. ISBN 978-0-8018-5414-9.
• (EN) Sparse Matrix Algorithms Research all'Università della Florida, che contiene la collezione di matrici sparse dell'università.

[modifica] Voci correlate

• Matrice grattacielo