File CsrMatrix.h

↰ Parent directory (ADS/numeric)

A sparse matrix in compressed sparse rows (CSR), beyond the book: the nonzeros of each row, by column, in one vector of values and one of columns, and the place where each row begins in a vector of m + 1 offsets, :math:` 12, nnz + 8, m ` bytes for doubles, read in order by the product with a vector instead of the walk of the orthogonal lists of SparseMatrix [see File SparseMatrix.h], whose nodes are scattered.

Definition (ADS/numeric/CsrMatrix.h)

Detailed Description

  • The matrix is built from triplets ( i , j , v ) in any order by a counting sort on the rows, a sort of the columns of each row and the sum of the equal places, O( nnz + m + sort ), or from a SparseMatrix.

  • multiply() is the product y = A x, by rows: the nonzeros stream from memory in one pass, the entries of x are read by column: :math:` 2,nnz ` operations on :math:` 12,nnz + 8 ( m + 1 ) ` bytes of the matrix, 8 m written and up to 8 nnz read of x, so that the product is bound by the memory, and on the benchmark neither more accumulators per row nor the gathers of AVX-512 made it faster.

  • transpose() is the CSR of the transpose, i.e., the matrix by columns, by a counting sort on the columns that keeps the rows sorted, O( nnz + m + n ); a large matrix whose rows span columns far apart (a sample of blocks of 64 rows decides) goes first into 256 buckets of consecutive columns and then each bucket into its slice of the transpose, two passes whose writes stay in few streams and in the cache instead of one pass of writes scattered over all the transpose (the partitioned radix sort of the databases): 2 nnz moves instead of nnz, but :math:` O( nnz / L ) ` misses instead of up to nnz, for lines of L items, when a slice of :math:` nnz / 256 ` items fits the cache.

The contracts [see File Contract.h]: the places of the triplets are in the matrix, and the columns fit 32 bits (the rows too, for transpose()); x has n entries; the invariant is that the offsets do not decrease and the columns of a row increase, an audit. The functions are defined in CsrMatrix.tpp.

  1. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, section 3.4

  1. Williams, L. Oliker, R. Vuduc, J. Shalf, K. Yelick, J. Demmel, Optimization of sparse matrix-vector multiplication on emerging multicore platforms, Parallel Computing 35(3), 178-194, 2009, doi:10.1016/j.parco.2008.12.006

  1. Polychroniou, K. A. Ross, A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort, Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, 755-766, 2014, doi:10.1145/2588555.2610522

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes