matrice sparsa - Sparse matrix

Esempio di matrice sparsa ${\displaystyle \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\x}}\fine {piccolo$

La matrice sparsa di cui sopra contiene solo 9 elementi diversi da zero, con 26 elementi nulli. La sua scarsità è del 74% e la sua densità è del 26%.

Una matrice sparsa ottenuta risolvendo un problema agli elementi finiti in due dimensioni. Gli elementi diversi da zero sono mostrati in nero.

Nell'analisi numerica e nel calcolo scientifico , una matrice sparsa o una matrice sparsa è una matrice in cui la maggior parte degli elementi è zero. Non esiste una definizione rigorosa riguardo alla proporzione di elementi di valore zero per una matrice da qualificare come sparsa, ma un criterio comune è che il numero di elementi diversi da zero è approssimativamente uguale al numero di righe o colonne. Al contrario, se la maggior parte degli elementi è diversa da zero, la matrice è considerata densa . Il numero di elementi a valore zero diviso per il numero totale di elementi (ad esempio, m × n per una matrice m × n) è talvolta indicato come scarsità della matrice.

Concettualmente, la scarsità corrisponde a sistemi con poche interazioni a coppie. Ad esempio, si consideri una linea di sfere collegate da molle da una all'altra: questo è un sistema sparso poiché solo le sfere adiacenti sono accoppiate. Al contrario, se la stessa linea di palline avesse delle molle che collegano ciascuna sfera a tutte le altre, il sistema corrisponderebbe a una matrice densa. Il concetto di sparsità è utile nella combinatoria e in aree applicative come la teoria delle reti e l'analisi numerica , che in genere hanno una bassa densità di dati o connessioni significativi. Matrici sparse di grandi dimensioni appaiono spesso in applicazioni scientifiche o ingegneristiche quando si risolvono equazioni differenziali alle derivate parziali .

Quando si memorizzano e si manipolano matrici sparse su un computer , è utile e spesso necessario utilizzare algoritmi e strutture dati specializzati che sfruttano la struttura sparsa della matrice. Sono stati realizzati computer specializzati per matrici sparse, poiché sono comuni nel campo dell'apprendimento automatico. Le operazioni che utilizzano strutture e algoritmi a matrice densa standard sono lente e inefficienti se applicate a matrici sparse di grandi dimensioni poiché l'elaborazione e la memoria vengono sprecate sugli zeri. I dati sparsi sono per natura più facilmente compressi e quindi richiedono uno spazio di archiviazione notevolmente inferiore . Alcune matrici sparse molto grandi sono impossibili da manipolare utilizzando algoritmi a matrice densa standard.

Memorizzazione di una matrice sparsa

Una matrice viene in genere archiviata come array bidimensionale. Ogni voce dell'array rappresenta un elemento a _{i , j} della matrice ed è accessibile dai due indici i e j . Convenzionalmente, i è l'indice di riga, numerato dall'alto verso il basso, e j è l'indice di colonna, numerato da sinistra a destra. Per una matrice m × n , la quantità di memoria necessaria per memorizzare la matrice in questo formato è proporzionale a m × n (a prescindere dal fatto che devono essere memorizzate anche le dimensioni della matrice).

Nel caso di una matrice sparsa, è possibile realizzare riduzioni sostanziali dei requisiti di memoria memorizzando solo le voci diverse da zero. A seconda del numero e della distribuzione delle voci diverse da zero, è possibile utilizzare diverse strutture di dati e ottenere enormi risparmi di memoria rispetto all'approccio di base. Il compromesso è che l'accesso ai singoli elementi diventa più complesso e sono necessarie strutture aggiuntive per poter recuperare in modo univoco la matrice originale.

I formati possono essere suddivisi in due gruppi:

• Quelli che supportano la modifica efficiente, come DOK (Dizionario di chiavi), LIL (Elenco di elenchi) o COO (Elenco di coordinate). Questi sono tipicamente usati per costruire le matrici.
• Quelli che supportano l'accesso efficiente e le operazioni di matrice, come CSR (Compressed Sparse Row) o CSC (Compressed Sparse Column).

Dizionario delle chiavi (DOK)

DOK consiste in un dizionario che mappa (riga, colonna) - si accoppia al valore degli elementi. Gli elementi che mancano dal dizionario sono considerati zero. Il formato è buono per costruire in modo incrementale una matrice sparsa in ordine casuale, ma scarso per l'iterazione su valori diversi da zero in ordine lessicografico. In genere si costruisce una matrice in questo formato e quindi si converte in un altro formato più efficiente per l'elaborazione.

Elenco delle liste (LIL)

LIL memorizza un elenco per riga, con ogni voce contenente l'indice della colonna e il valore. In genere, queste voci vengono mantenute ordinate per indice di colonna per una ricerca più rapida. Questo è un altro formato utile per la costruzione di matrici incrementali.

Elenco coordinate (COO)

COO memorizza un elenco di tuple (riga, colonna, valore) . Idealmente, le voci vengono ordinate prima per indice di riga e poi per indice di colonna, per migliorare i tempi di accesso casuale. Questo è un altro formato utile per la costruzione di matrici incrementali.

Riga sparsa compressa (formato CSR, CRS o Yale)

Il formato riga compresso sparso (CSR) o archiviazione riga compressa (CRS) o Yale rappresenta una matrice M per tre matrici (unidimensionali), che contengono rispettivamente valori diversi da zero, le estensioni delle righe e gli indici delle colonne. È simile a COO, ma comprime gli indici di riga, da cui il nome. Questo formato consente l'accesso rapido alle righe e le moltiplicazioni vettore matrice ( M x ). Il formato CSR è in uso almeno dalla metà degli anni '60, con la prima descrizione completa che appare nel 1967.

Il formato CSR memorizza una matrice sparsa m × n M sotto forma di riga utilizzando tre array ( unidimensionali) (V, COL_INDEX, ROW_INDEX) . Sia NNZ il numero di elementi diversi da zero in M . (Si noti che qui devono essere utilizzati indici a base zero .)

• Gli array V e COL_INDEX sono di lunghezza NNZ e contengono rispettivamente i valori diversi da zero e gli indici di colonna di tali valori.

• L'array ROW_INDEX è di lunghezza m + 1 e codifica l'indice in V e COL_INDEX dove inizia la riga data. Questo è equivalente a ROW_INDEX[j] che codifica il numero totale di valori diversi da zero sopra la riga j . L'ultimo elemento è NNZ , cioè l'indice fittizio in V subito dopo l'ultimo indice valido NNZ - 1 .

Ad esempio, la matrice

${\displaystyle {\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}}$

è una matrice 4 × 4 con 4 elementi diversi da zero, quindi

   V         = [ 5 8 3 6 ]
   COL_INDEX = [ 0 1 2 1 ]
   ROW_INDEX = [ 0 1 2 3 4 ] 

supponendo un linguaggio a indice zero.

Per estrarre una riga, definiamo prima:

   row_start = ROW_INDEX[row]
   row_end   = ROW_INDEX[row + 1]

Quindi prendiamo le sezioni da V e COL_INDEX a partire da row_start e terminando con row_end.

Per estrarre la riga 1 (la seconda riga) di questa matrice impostiamo row_start=1e row_end=2. Quindi facciamo le fette V[1:2] = [8]e COL_INDEX[1:2] = [1]. Ora sappiamo che nella riga 1 abbiamo un elemento nella colonna 1 con valore 8.

In questo caso la rappresentazione CSR contiene 13 voci, rispetto alle 16 della matrice originale. Il formato CSR salva in memoria solo quando NNZ < ( m ( n − 1) − 1) / 2 . Un altro esempio, la matrice

${\displaystyle {\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}}$

è una matrice 4 × 6 (24 voci) con 8 elementi diversi da zero, quindi

   V         = [ 10 20 30 40 50 60 70 80 ]
   COL_INDEX = [  0  1  1  3  2  3  4  5 ]   
   ROW_INDEX = [  0  2  4  7  8 ]

Il tutto viene memorizzato come 21 voci.

• ROW_INDEX divide l'array V in righe: (10, 20) (30, 40) (50, 60, 70) (80);
• COL_INDEX allinea i valori nelle colonne: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Nota che in questo formato, il primo valore di ROW_INDEX è sempre zero e l'ultimo è sempre NNZ , quindi sono in un certo senso ridondanti (sebbene nei linguaggi di programmazione in cui la lunghezza dell'array debba essere esplicitamente memorizzata, NNZ non sarebbe ridondante). Tuttavia, ciò evita la necessità di gestire un caso eccezionale quando si calcola la lunghezza di ciascuna riga, poiché garantisce che la formula ROW_INDEX[ i + 1] − ROW_INDEX[ i ] funzioni per qualsiasi riga i . Inoltre, il costo della memoria di questa memoria ridondante è probabilmente insignificante per una matrice sufficientemente grande.

I (vecchi e nuovi) formati a matrice sparsa di Yale sono istanze dello schema CSR. Il vecchio formato Yale funziona esattamente come descritto sopra, con tre array; il nuovo formato combina ROW_INDEX e COL_INDEX in un unico array e gestisce separatamente la diagonale della matrice.

Per le matrici di adiacenza logica , l'array di dati può essere omesso, poiché l'esistenza di una voce nell'array di righe è sufficiente per modellare una relazione di adiacenza binaria.

È probabilmente noto come il formato Yale perché è stato proposto nel rapporto Yale Sparse Matrix Package del 1977 dal Dipartimento di Informatica dell'Università di Yale.

Colonna sparsa compressa (CSC o CCS)

CSC è simile a CSR tranne per il fatto che i valori vengono letti prima per colonna, viene archiviato un indice di riga per ogni valore e vengono archiviati i puntatori di colonna. Ad esempio, CSC è (val, row_ind, col_ptr) , dove val è un array dei valori (dall'alto verso il basso, quindi da sinistra a destra) diversi da zero della matrice; row_ind sono gli indici di riga corrispondenti ai valori; e col_ptr è l'elenco degli indici val in cui inizia ogni colonna. Il nome si basa sul fatto che le informazioni sull'indice di colonna sono compresse rispetto al formato COO. Di solito si usa un altro formato (LIL, DOK, COO) per la costruzione. Questo formato è efficiente per operazioni aritmetiche, suddivisione in colonne e prodotti vettore matrice. Vedere scipy.sparse.csc_matrix . Questo è il formato tradizionale per specificare una matrice sparsa in MATLAB (tramite la sparsefunzione).

Struttura speciale

fasciato

Un importante tipo speciale di matrici sparse è la matrice a bande , definita come segue. La larghezza di banda inferiore di una matrice A è il numero più piccolo p tale che la voce a _{i , j} svanisce ogni volta che i > j + p . Allo stesso modo, la larghezza di banda superiore è il numero più piccolo p tale che a _{i , j} = 0 ogni volta che i < j − p ( Golub & Van Loan 1996 , §1.2.1). Ad esempio, una matrice tridiagonale ha larghezza di banda inferiore 1 e larghezza di banda superiore 1 . Come altro esempio, la seguente matrice sparsa ha larghezza di banda inferiore e superiore entrambe uguali a 3. Notare che gli zeri sono rappresentati con punti per chiarezza.

${\displaystyle \left({\begin{smallmatrix}X&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&X&\cdot &\cdot &\\X&\cdot &X&\cdot &X&\cdot &\ cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&X&\\\cdot &\cdot &\cdot &X&X&X&\cdot &\\\cdot &\cdot &\cdot &\ cdot &X&\cdot &X&\\\end{matrice piccola}}\destra)}$

Le matrici con larghezza di banda superiore e inferiore ragionevolmente piccola sono note come matrici a banda e spesso si prestano ad algoritmi più semplici rispetto alle matrici sparse generali; oppure a volte si possono applicare algoritmi a matrice densa e guadagnare efficienza semplicemente eseguendo il loop su un numero ridotto di indici.

Riordinando le righe e le colonne di una matrice A può essere possibile ottenere una matrice A ′ con una larghezza di banda inferiore. Numerosi algoritmi sono progettati per ridurre al minimo la larghezza di banda .

Diagonale

Una struttura molto efficiente per un caso estremo di matrici a bande, la matrice diagonale , consiste nel memorizzare solo gli elementi nella diagonale principale come un array unidimensionale , quindi una matrice diagonale n × n richiede solo n elementi.

Simmetrico

Una matrice sparsa simmetrica nasce come matrice di adiacenza di un grafo non orientato ; può essere memorizzato in modo efficiente come un elenco di adiacenze .

Blocco diagonale

Una matrice diagonale a blocchi è costituita da sottomatrici lungo i suoi blocchi diagonali. Una matrice diagonale a blocchi A ha la forma

${\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1}&0&\cdots &0\\0&\mathbf {A} _{2}&\cdots &0\\\vdots &\ vdots &\ddots &\vdots \\0&0&\cdots &\mathbf {A} _{n}\end{bmatrix}},}$

dove A _k è una matrice quadrata per ogni k = 1, ..., n .

Ridurre il riempimento

I fill-in di una matrice sono quelle voci che cambiano da un valore iniziale zero a un valore diverso da zero durante l'esecuzione di un algoritmo. Per ridurre i requisiti di memoria e il numero di operazioni aritmetiche utilizzate durante un algoritmo, è utile ridurre al minimo il riempimento scambiando righe e colonne nella matrice. La scomposizione simbolica di Cholesky può essere utilizzata per calcolare il peggior riempimento possibile prima di eseguire l'effettiva scomposizione di Cholesky .

Esistono altri metodi oltre alla decomposizione di Cholesky in uso. I metodi di ortogonalizzazione (come la fattorizzazione QR) sono comuni, ad esempio, quando si risolvono problemi con i metodi dei minimi quadrati. Sebbene la compilazione teorica sia sempre la stessa, in termini pratici i "falsi non zero" possono essere diversi per metodi diversi. E le versioni simboliche di quegli algoritmi possono essere utilizzate allo stesso modo del Cholesky simbolico per calcolare il riempimento del caso peggiore.

Risolvere equazioni a matrice sparsa

Entrambi iterativi esistono metodi e diretti per sparse solving matrice.

I metodi iterativi, come il metodo del gradiente coniugato e GMRES, utilizzano calcoli veloci di prodotti matrice-vettore , in cui la matrice è sparsa. L'uso di precondizionatori può accelerare significativamente la convergenza di tali metodi iterativi. ${\displaystyle Ascia_{i}}$${\displaystyle A}$

Software

Molte librerie software supportano matrici sparse e forniscono solutori per equazioni di matrici sparse. Sono open source:

• SuiteSparse , una suite di algoritmi a matrice sparsa, orientata alla soluzione diretta di sistemi lineari sparsi.
• PETSc , una grande libreria C, contenente molti diversi risolutori di matrici per una varietà di formati di archiviazione a matrice.
• Trilinos , una grande libreria C++, con sotto-librerie dedicate all'archiviazione di matrici dense e sparse e alla soluzione dei corrispondenti sistemi lineari.
• Eigen3 è una libreria C++ che contiene diversi solutori di matrici sparse. Tuttavia, nessuno di questi è parallelizzato .
• MUMPS ( MU ltifrontal M assively P arallel sparse diretta S Olver), scritto in Fortran90, è un risolutore frontale .
• DUNE , una libreria di elementi finiti che ha anche una sotto-libreria per i sistemi lineari sparsi e la loro soluzione.
• Pastix .
• SuperLU .
• Armadillo fornisce un wrapper C++ intuitivo per BLAS e LAPACK.
• SciPy fornisce supporto per diversi formati di matrici sparse, algebra lineare e risolutori.
• SPArse Matrix (spam) Pacchetto R e Python per matrici sparse.
• Wolfram Language Tools per la gestione di array sparsi
• ALGLIB è una libreria C++ e C# con supporto per l'algebra lineare sparsa
• Libreria ARPACK Fortran 77 per la diagonalizzazione e la manipolazione di matrici sparse, utilizzando l'algoritmo di Arnoldi
• SPARSE Riferimento (vecchio) pacchetto NIST per la diagonalizzazione di matrici sparse (reali o complesse)
• Libreria SLEPc per la soluzione di sistemi lineari su larga scala e matrici sparse
• Sympiler , un generatore di codice e una libreria specifici del dominio per la risoluzione di sistemi lineari e problemi di programmazione quadratica.
• Scikit-learn Un pacchetto Python per l'analisi dei dati che include matrici sparse.

Storia

Il termine matrice sparsa fu probabilmente coniato da Harry Markowitz che iniziò alcuni lavori pionieristici ma poi lasciò il campo.

Guarda anche

Appunti

Riferimenti

• Golub, Gene H. ; Van Loan, Charles F. (1996). Calcoli di matrici (3a ed.). Baltimora: Johns Hopkins. ISBN 978-0-8018-5414-9.
• Stoer, Josef; Bulirsch, Roland (2002). Introduzione all'analisi numerica (3a ed.). Berlino, New York: Springer-Verlag . ISBN 978-0-387-95452-3.
• Tewarson, Reginald P. (maggio 1973). Matrici sparse (parte della serie Mathematics in Science & Engineering) . Academic Press Inc. (Questo libro, di un professore della State University di New York presso Stony Book, è stato il primo libro dedicato esclusivamente alle Matrici sparse. I corsi di laurea che lo utilizzavano come libro di testo venivano offerti in quell'università all'inizio degli anni '80).
• Banca, Randolph E.; Douglas, Craig C. "Pacchetto di moltiplicazione di matrici sparse" (PDF) .
• Pissanetzky, Sergio (1984). Tecnologia a matrice sparsa . stampa accademica.
• Snay, Richard A. (1976). "Ridurre il profilo delle matrici simmetriche sparse". Bollettino geodetico . 50 (4): 341–352. Bibcode : 1976BGeod..50..341S . doi : 10.1007/BF02521587 . hdl : 2027/uc1.31210024848523 . S2CID  123079384 . Anche NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.

Ulteriori letture

• Gibbs, Norman E.; Poole, William G.; Stockmeyer, Paul K. (1976). "Un confronto tra diversi algoritmi di riduzione della larghezza di banda e del profilo" . Transazioni ACM su software matematico . 2 (4): 322-330. doi : 10.1145/355705.355707 . S2CID  14494429 .
• Gilbert, John R.; Moler, Cleve; Schreiber, Robert (1992). "Matrici sparse in MATLAB: progettazione e implementazione" . SIAM Journal sull'analisi e le applicazioni della matrice . 13 (1): 333-356. CiteSeerX  10.1.1.470.1054 . doi : 10.1137/0613024 .
• Ricerca sugli algoritmi della matrice sparsa presso la Texas A&M University.
• SuiteSparse Matrix Collection
• Progetto SMALL Un progetto finanziato dall'UE su modelli sparsi, algoritmi e apprendimento di dizionari per dati su larga scala.