Detta papper introducerar ett lagringsformat för glesa matriser, så kallade komprimerade glesa block (CSB), som gör att både Ax och A T x kan beräknas effektivt parallellt, där A är en n × n gles matris med nnz ≥ n nonzeros och x är en tät n-vektor. Våra algoritmer använder sig av arbete (nnz) (serial running time) och spännvidd (kritisk-path längd), vilket ger en parallellism av  till (nnz / ε n lg n), som är tillräckligt hög för praktiskt taget alla stora matriser. Lagringskravet för CSB är i stort sett detsamma som för det mer standardiserade formatet för komprimerade rader (CSR), för vilket det är enkelt att beräkna Ax parallellt men A T x är svårt. Benchmark resultat indikerar att på en processor, CSB algoritmer för Ax och A T x köra lika snabbt som CSR algoritm för Ax, men CSB algoritmer också skala upp linjärt med processorer tills begränsas av offchip minne bandbredd.
Vårt multi-nivå komprimerade sparse lagringsformat har en anslutning till Compressed Sparse Block (CSB) system av Buluç et al. Hoppa över det.
Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks
{'venue': "SPAA '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}