Sparse-Matrix-Multiplication

Code for heterogeneous computing of product of two sparse matrices

Algorithm: Gustavson’s Row-wise SpGEMM 3

Input: Sparse matrices A and B

Output: Sparse matrix C

 
set matrix C to ∅
for all a i ∗ in matrix A in parallel do
  for all a ik in row a i ∗ do
    for all b k j in row b k ∗ do
            value ← a ik b k j
            if c i j #∈ c i ∗ then
                insert ( c i j ← v alue ) to c i ∗
            else
                c i j ← c i j + value
            end if
        end for
    end for
end for

Algorithm 2 RowsToThreads.

Input: Sparse matrices A and B

Output: Array o f f set

{1. Set FLOP vector}
for i ← 0 to m in parallel do
    flop [ i ] ← 0
    for j ← r pts A [ i ] to r pts A [ i + 1] do
        rnz ← r pts B [ cols A [ j] + 1] − r pt B [ cols A [ j]]
        flop [ i ] ← flop [ i ] + rnz
    end for
end for
{ 2 . Assign rows to thread }
flop ps ← ParallelPrefixSum ( flop )
sum flop ← flop ps [ m ]
tnum ← omp_get_max_threads ()
a v e flop ← sum flop / tnum
o f f set[0] ← 0
for tid ← 1 to tnum in parallel do
    o f f set [ tid ] ← lowbnd ( flop ps , a v e flop ∗ tid )
end for
o f f set [ t num ] ← m

Algorithm : Hash SpGEMM.

Input: Sparse matrices A and B

Output: Sparse matrix C

off set ← RowsToThreads ( A, B )
{Determine hash-table size for each thread}
tnum ← omp_get_max_threads ()
for tid ← 0 to tnum in parallel do
    size t ← 0
    for i ← o f f set [ t id] to o f f set [ t id + 1] do
        size t ← max ( size t , flop [ i ] )
    end for
    {Required maximum hash-table size is N col }
    size t ← min ( N col , size t )
    {Return minimum 2 n so that 2 n > size t }
    size t ← lowest_p2 ( size t )
end for
Symbolic ( r pts C , A, B )
Numeric ( C, A, B )