Sparse Matrix e la sua rappresentazione 3-pla

Question

Questa matrice sparsa e la sua rappresentazione 3-tuple non è sempre nella mia testa ... O la sua po 'complicato o le mie risorse da dove sto studiando non sono poi così bene ... qui è l'URI Sparse Matrix scorrere

Quindi, se avete qualche cosa da condividere si prega di andare avanti.

Grazie

Answer 1

La presentazione ppt si fa riferimento è piuttosto semplice. Le idee di base è che si desidera solo per registrare le voci di matrice che non sono pari a zero. Naturalmente, si salta un mazzo di 0 voci, quindi è necessario registrare anche gli indici di riga e colonna insieme al non-zero-valore.

Si presenta un paio di modi per farlo. Uno è solo un lungo elenco, con le voci ordinate per riga allora colonna. Poi guarda le prestazioni di un paio di operazioni di matrice.

1) Trasposizione è abbastanza veloce; solo una sorta dell'elenco sugli indici di colonna quindi sostanzialmente riga. 2) aggiunta di due matrici è anche veloce; si attraversano le due liste dei due matrici insieme aggiungendo valori in modo appropriato, come una sorta di fusione delle due liste ordinate. Si noti che si attraversano solo ogni lista una volta.

Queste due operazioni hanno un po 'più lungo per l'opzione lista collegata.

Queste operazioni prendere troppo sopravvalutato più quando si utilizza una matrice di piena nella memoria, perché si sta fondamentalmente paging dentro e fuori quasi continuamente, che è molto più lento di lavorare per lo più nella memoria cache maggiore velocità.

Non sa misurare le prestazioni di moltiplicazione di matrici o di calcolo l'inverso. Forse queste operazioni non sono di solito necessari nelle applicazioni che utilizzano matrici sparse. Forse si può pensare a loro come un esercizio.