moltiplicazione matrice sparse veloce

Question

per la classe Devo scrivere il mio risolutore di equazioni lineari per matrici sparse. Sono libero di utilizzare qualsiasi tipo di struttura dati per matrici sparse e devo implementare diversi risolti, incluso il gradiente coniugato.

Mi chiedevo se esiste un modo famoso per memorizzare matrici sparse in modo tale che la moltiplicazione con un vettore sia relativamente veloce.

In questo momento le mie matrici sparse sono fondamentalmente implementate con un std::map< std::pair<int, int>, double> impacchettato che memorizza i dati, se presenti. Questo trasforma la moltiplicazione di una matrice con dal vettore in una complessità di O (n²) in una O (n²log (n)) poiché devo eseguire la ricerca di ogni elemento della matrice. Ho esaminato il formato della matrice Sparse Yale e sembra che il recupero di un elemento sia anche in O (log (n)) quindi non sono sicuro se sarebbe molto più veloce.

Per riferimento, ho una matrice 800x800 che viene popolata con 5000 voci. Ci vogliono circa 450 secondi per risolvere un tale sistema con il metodo del gradiente coniugato.

Pensi che sia possibile farlo molto più rapidamente con un'altra struttura dati?

grazie!

Answer 1

Le scelte più comuni sono CSC or CSR storage. Questi sono entrambi efficienti per la moltiplicazione di matrice vettoriale. È anche molto facile codificare le routine di moltiplicazione, se devi farlo tu stesso.

Detto questo, lo storage Yale offre anche un moltiplicatore di matrice vettoriale molto efficiente. Se stai eseguendo la ricerca di elementi matrix, hai frainteso come utilizzare il formato. Vi suggerisco di studiare alcune delle librerie sparse standard per imparare come viene implementata la moltiplicazione della matrice vettoriale.

Anche con la memoria corrente è possibile eseguire la moltiplicazione della matrice in complessità O (n). Tutti gli algoritmi di moltiplicazione con matrice a matrice sparsa che ho mai visto si riducono agli stessi passaggi. Ad esempio, considera y = Ax.

1. Azzerare il vettore del risultato, y.
2. Inizializzare un iteratore per gli elementi diversi da zero della matrice, A.
3. Ottenere il prossimo elemento diverso da zero della matrice, A [i, j] dire. Si noti che il modello di i, j non segue uno schema regolare. Riflette semplicemente l'ordine in cui sono memorizzati gli elementi diversi da zero di A.
4. y [i] + = A [i, j] * x [j]
5. Se ci sono più elementi di A, goto 3.

Ho il sospetto che si sta scrivendo il classico doppio ciclo for codice moltiplicazione denso:

for (i=0; i<N; i++) 
    for (j=0; j<N; j++) 
     y[i] += A[i,j]*x[j] 

ed è quello che sta portando di eseguire le ricerche.

Ma non sto suggerendo di rimanere con lo spazio di archiviazione std::map. Non sarà super efficiente. Consiglierei CSC principalmente perché è il più usato.