Formati per la memorizzazione di matrici sparse

Questo dovrebbe funzionare bene quando si attraversa la matrice CSR avanti riga per riga, in quanto si può semplicemente mantenere un indice accumulato. Avrai bisogno di una variabile contatore aggiuntiva, che la maggior parte dei processori dovrebbe facilmente ospitare; non aggiunge nemmeno un riferimento di memoria al loop interno.

Ecco il ciclo interno della matrice sparsa comune per il moltiplicatore vettoriale denso:

for (i = 0; i < N; i++)
{  
    for (k = RowPtr[i]; k < RowPtr[i+1]; k++)
    {  
        result[i] += Val[k]*d[Col[k]];
    }  
}  

Questo cambierebbe in:

k = Count[0];
for (i = 0; i < N; i++)
{ 
    for (count = Count[i+1]; --count >= 0; k++)
    {  
        result[i] += Val[k]*d[Col[k]];
    }  
}  

Posso pensare a due inconvenienti:

1. Se alcuni algoritmi richiedevano un accesso seriamente casuale, potresti voler creare un array RowPtr temporaneo da utilizzare. (Certo, cerchiamo di evitare quegli algoritmi perché non sono cache friendly.)
2. Essendo un formato non standard, la possibilità di utilizzare librerie (come Eigen ) potrebbe essere limitata, ma ancora una volta potresti essere in grado di convertire quando necessario.

Formato CSR:

Il formato CSR utilizza un puntatore a riga per individuare rapidamente un elemento. Per trovare l'elemento [i, j] richiede:

• 1 accesso indicizzato per ottenere il "puntatore" di riga (sfasamento di riga, in un AI dell'array)
• numero massimo di accessi indicizzati all'indice della colonna (nell'array AJ) per trovare la colonna corrispondente
• 1 accesso indicizzato per ottenere l'elemento (nell'array A) se non è zero.

Se per qualsiasi motivo sei interessato al numero di valori diversi da zero nella riga i, devi fare una sola operazione matematica: A [i] -A [i-1] (o A [i + 1] -A [i] se si avvia io a 1).

La difficoltà è se imposti nuovi valori non nulli nella matrice: devi incrementare tutti i "puntatori" di riga dopo la riga in cui stai inserendo, e devi inserire l'indice della colonna e il valore (che implica lo spostamento del oggetti che vengono dopo).

Il tuo nuovo formato

Si intende tenere traccia del numero di elementi diversi da zero in ogni riga, invece del "puntatore" di riga. Questo è perfettamente fattibile: basta interpretare A in modo diverso.

Lo svantaggio sarà che l'accesso a un elemento nella riga i, richiederebbe quindi ogni volta di sommare tutte le A [n] per n tra 0 e i-1. Quindi dovrai fare molte aggiunte. Ogni volta che accedi a un elemento. Questo sarà molto meno efficiente della CSR.