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.
Dessutom, Buluç et al. använda blockeringar och arbetsytor för att utveckla glesa multiplikationsalgoritmer för CSB-datastrukturen som är lika snabba för Ax och A T x REF ].
Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks
{'venue': "SPAA '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}