Sparse matrices, sparse accumulator and multiplication

2
votes

I'm trying to implement the algorithm for multiplying two sparse matrices from this paper: https://crd.lbl.gov/assets/pubs_presos/spgemmicpp08.pdf (the first algorithm - 1D algorithm).

What bothers me is that I'm not sure what SPA (sparse accumulator) really is. I've done some research and what I've concluded is that SPA represents a ???????????????????????? row/column of a sparse matrix (I'm mostly not sure about that part) and that it consists of a dense vector with nonzero values, a list of indices of nonzero elements (why list?) and a bool dense vector consisting of "occupied" flags (???????????????? on ????-th index if an element in the active row/column on that position is not zero). Some also keep the number of nonzero inputs.

Am I correct? If so, I have some questions. If this structure has a dense boolean vector and we must keep the values, isn't it easier to simply fill one dense vector and ignore that it's sparse? I'm sure that there are reasons why this is more efficient (memory and time), but I don't see why.

Also, as I've already asked, why is everything a vector except the list of indices? Why isn't that also a vector?

Thanks in advance!

1
sparse-matrixmatrix-multiplication

1 Answers

1
votes

Many sparse matrix algorithms use a dense working vector to allow random access to the currently "active" column or row of a matrix.

The sparse MATLAB implementation formalizes this idea by defining an abstract data type called the sparse accumulator, or SPA. The SPA consists of a dense vector of real (or complex) values, a dense vector of true/false "occupied" flags, and an unordered list of the indices whose occupied flags are true. The SPA represents a column vector whose "unoccupied" positions are zero and whose "occupied" positions have values (zero or nonzero) specified by the dense real or complex vector. It allows random access to a single element in constant time, as well as sequencing through the occupied positions in constant time per element.

Check section 3.1.3 at https://epubs.siam.org/doi/pdf/10.1137/0613024