Algoritmo per moltiplicazione di matrice di forme quadratiche con matrice sparsa

Question

Sto ottimizzando il codice che fa molto affidamento su una libreria Matrix fatta su misura (che non sarà esclusa dal progetto perché è ovunque.Non è bello, ma è un dato di fatto. ..) molti i calcoli sono fatti con matrici di 10-20 righe e colonne, molti calcoli includono una forma quadratica come

C = A*B*A' 

mi sono reso conto che spesso una è scarsa e mi piacerebbe fare uso di questo fatto. Quindi sto cercando un algoritmo che gestisca questo caso. La stabilità numerica è importante. C'è qualcosa che posso usare? (Non ho scritto la nostra libreria quindi non so se ci sono delle insidie ​​che dovrei prendere in considerazione?)

Come "il nostro" semplice metodo di moltiplicazione O (n^3) viene eseguito più velocemente di Eigen 3 in la piattaforma di destinazione, poiché ho bisogno di stabilità numerica e le matrici non sono molto grandi, suppongo che l'algoritmo di Strassen e l'algoritmo di Coppersmith-Winograd non siano ciò che sto cercando. Invece è solo la moltiplicazione della forma quadratica in un modo che mi permette di controllare facilmente gli zeri in A.

Grazie per qualsiasi suggerimento!

Answer 1

Esiste this carta, che si occupa della moltiplicazione di matrice sparsa veloce. L'algoritmo sviluppato divide la matrice sparsa in due parti: una densa e una sparsa e applica un algoritmo di moltiplicazione veloce su di essa. Quindi per me sembra che non dipenda dalla dimensione della matrice, come hai menzionato rispetto a Strassen, ma dal fatto che è scarna.

Answer 2

Esistono modi per implementare una matrice sparsa in modi che rendono più condensata di una matrice densa. Un modo che lo faccio è la seguente:

[0 0 0 0 0] 
[0 1 2 0 9] 
[0 0 0 2 0] 
[0 1 0 0 0] 

diventa lineare degli elementi non nulli

typedef struct { 
    int row; 
    int col; 
    double entry; 
} Element; 

typedef SparseMatrix Element*; 

Quindi la matrice ha ora una complessità spazio di O (n) invece di O (n^2) Per A * B, dove A e B sono matrici, è sufficiente attraversare ogni matrice per gli elementi corrispondenti (es. a-> row == b-> col & & a-> col == b-> riga), ed eventualmente aggiungere diversi insieme (prodotto interno). Questo algoritmo sarebbe di complessità O (n^2) piuttosto che O (n^3). Questo perché è possibile saltare la frivola operazione di prendere un prodotto interno che risulterebbe pari a zero.

Answer 3

check out Highly Parallel Sparse Matrix-Matrix Multiplication algorothm