Caso non simmetrico

Data una generica matrice $A$ quadrata di ordine $n$, la tecnica di memorizzazione CRS prevede la generazione di 3 vettori:

1. SYSMAT: vettore di numeri reali contenente gli $nt$ coefficienti non nulli della matrice $A$ memorizzati in successione per righe;
2. JA: vettore di numeri interi contenente gli $nt$ indici di colonna dei corrispondenti elementi memorizzati in SYSMAT;
3. IA: vettore di numeri interi con $n+1$ componenti, contenente le posizioni in cui si trova in SYSMAT il primo elemento di ciascuna riga di $A$.

Il vettore IA è chiamato ``vettore topologico'' e talvolta indicato anche come TOPOL. L'uso congiunto di IA e JA consente di individuare qualsiasi elemento non nullo $a_{ij}$ memorizzato in SYSMAT. Infatti, l'elemento $a_{ij}$ si troverà in una posizione $k$ del vettore SYSMAT compresa nell'intervallo IA $(i) \leq k \leq$ IA$(i+1)-1$ e tale per cui JA$(k)=j$. Queste due condizioni permettono di individuare univocamente $k$ per cui SYSMAT $(k)=a_{ij}$. Si noti che l'occupazione di memoria si riduce da $n^2$ numeri reali (generalmente in doppia precisione) a $nt$ numeri reali (tipicamente $nt < 0.05 n^2$) e $nt+n+1$ numeri interi.

Facciamo un esempio numerico per rendere più chiaro il concetto. Si consideri la seguente matrice $A$ di dimensione 6$\times$6, sparsa e non simmetrica:

$$A = \left[ \begin{array}{rrrrrr} 4 & 0 & 7 & 0 & 0 & 0 \\ 3 & 4 ... ... 0 & 1 \\ 1 & 0 & 0 & 3 & 4 & 0 \\ 1 & 1 & 0 & 0 & 3 & 4 \end{array} \right]$$

Gli elementi non nulli sono $nt=18$, mentre $n^2=36$, pertanto il grado di sparsità di $A$ è il 50%. Trascurando i coefficienti nulli, la matrice $A$ diventa:

$$A' = \left[ \begin{array}{rrrrrr} 4 & & 7 & & & \\ 3 & 4 & & 2 &... ... & & 7 & 4 & & 1 \\ 1 & & & 3 & 4 & \\ 1 & 1 & & & 3 & 4 \end{array} \right]$$

Il vettore SYSMAT ha dimensione 18 e risulta:

$$\overbrace{ \begin{array}{rrrrrrrrrrrrrrrrrr} 4 & 7 & 3 & 4 & 2 & 2 & 4 & 4 & 7 & 4 & 1 & 1 & 3 & 4 & 1 & 1 & 3 & 4 \end{array}}^{nt}$$

Il vettore JA ha la stessa dimensione di SYSMAT e per ogni coefficiente di quest'ultimo individua l'indice di colonna:

$$\overbrace{ \begin{array}{rrrrrrrrrrrrrrrrrr} 1 & 3 & 1 & 2 & 4 & 2 & 3 & 5 & 3 & 4 & 6 & 1 & 4 & 5 & 1 & 2 & 5 & 6 \end{array}}^{nt}$$

Il vettore IA, infine, individua la posizione in SYSMAT del primo coefficiente di ciascuna riga:

$$\overbrace{ \begin{array}{rrrrrrr} 1 & 3 & 6 & 9 & 12 & 15 & 19 \end{array}}^{n+1}$$

Si noti che che le componenti di IA sono necessariamente ordinate in senso strettamente crescente e che IA $(n+1)=nt+1$. Ciò si deduce immediatamente dal fatto che per individuare un elemento $a_{ij}$ dell'ultima riga di $A$ si deve cercare l'indice $k$ della componente in SYSMAT nell'intervallo IA $(n) \leq k \leq$ IA$(n+1)-1$.