Matrici Sparse e metodi iterativi di Jacobi e Gauss-Seidel

I metodi più efficienti per risolvere un sistema di tipo sparso sono quelli che non effettuano operazioni inutili coinvolgenti gli elementi nulli in esse presenti. Un metodo diretto come il classico algoritmo di Gauss non possiede tale caratteristica. Esso modifica la matrice dei coefficienti non preservandone la sparsità, poiché genera elementi non nulli in corrispondenza di elementi nulli della matrice originaria (fenomeno detto riempimento o fill in). La principale caratteristica di un metodo di risoluzione di un sistema sparso è quella di non modificare la matrice dei coefficienti così da ridurre complessità di tempo e spazio. Si possono così usare le particolari tecniche di memorizzazione (CSR e CSC ad esempio viste nel precedente articolo) che riducono la complessità di spazio e consentono una “facile gestione” in memoria di sistemi di grandi dimensioni. La sparsità di una matrice si può perdere se si eseguono alcune operazioni di algebra lineare, come l’algoritmo di Gauss e la fattorizzazione LU, con i quali otteniamo una matrice trasformata ed i fattori L ed U molto più “pieni” della matrice di partenza. Quindi, se il sistema è sparso e di grandi dimensioni è necessario l’utilizzo di metodi che non alterano la struttura della matrice e non effettuano operazioni su elementi nulli. I metodi usati per risolvere sistemi sparsi di grandi dimensioni sono metodi iterativi. Essi generano, a partire da una approssimazione iniziale, una successione di vettori che, in opportune ipotesi, converge alla soluzione del sistema. Una tecnica generale per costruire la successione di vettori è basata sullo splitting della matrice dei coefficienti. A seconda dello splitting generato si distinguono diversi metodi iterativi. Non scendiamo nel dettaglio della descrizione degli algoritmi, riportando alcuni link che si occupano di analizzare il formalismo algoritmico. Di seguito si riporta l’archivio contenente gli elaborati che in MATLAB implementano i metodi iterativi di Jacobi e Gauss-Seidel, sviluppati per l’esame di Calcolo Numerico 2. L’unica differenza che ci preme far notare rispetto ai link riportati è che nel caso Gauss-Seidel lo splitting da noi considerato è leggermente diverso: M=D+L e N=-U.

[dm]3[/dm]

Matrici Sparse e loro memorizzazione in MATLAB (CSR, CSC)

Per matrice sparsa si intende una matrice formata da molti elementi nulli. Ne consegue che gli elementi davvero importanti per queste matrici nell’ambito di un’elaborazione numerica sono pochi se raffrontati alle dimensioni della maggior parte dei sistemi in gioco nel mondo reale. Nell’ambito delle matrici sparse distinguiamo sostanzialmente due categorie. Possiamo avere matrici sparse strutturate, ovvero quelle per le quali la disposizione dei relativi elementi non nulli segue delle regole ben precise (matrici tridiagonali, a banda etc.). Simmetricamente è possibile definire matrici sparse non strutturate quelle per le quali la disposizione dei relativi elementi non nulli non segue un criterio preciso. E’ proprio per questa seconda categoria che sono stati introdotti alcuni metodi di memorizzazione particolari che consentono un notevole risparmio di spazio. In particolare se nnz è il numero di elementi non nulli di una matrice sparsa di dimensioni nxn questi metodi consentono di occupare per la memorizzazione della matrice uno spazio di memoria proprio proporzionale a nnz e non al prodotto delle dimensioni. In particolare è possibile distinguere tra formato di memorizzazione CSR, ovvero Compressed Sparse Row Format, e CSC, ovvero Compressed Sparse Column Format. Come si può ben comprendere tali metodi sono duali. Il primo consente di memorizzare gli elementi non nulli per righe, il secondo, invece, per colonne. Il sistema di calcolo MATLAB adopera il metodo CSC per la memorizzazione delle matrici sparse.

Di seguito riporto il link all’archivio contenente gli elaborati prodotti riguardo questo argomento per l’esame di Calcolo Numerico 2 con riferimento alla versione r2007b dell’ambiente di calcolo MATLAB:

[dm]2[/dm]