Are there any algorithms that allow efficient creation (element filling) of sparse (e.g. CSR or coordinate) matrix in parallel?
A:
If you store your matrix as a coordinate map, any language which has a concurrent dictionary implementation available should do the job for you.
Java's got the ConcurrentHashMap
, and .NET 4 has ConcurrentDictionary
, both of which allow multi-threaded non-blocking (afaik) element insertion in parallel.
tzaman
2010-08-01 12:40:18
Concurrency and parallelism are not the same thing.The problem here is truly data-parallel filling of elements into a sparse matrix.Specifically in my case I want to implement it on GPUs.
Fic Firic
2010-08-01 19:42:29
A:
There are no efficient algorithms for creating sparse matrices in data-parallel way. Plausible is coordinate matrix type which requires sorting after content filling, but that type is slow for matrix products etc.
Solution is you don't build sparse matrix - you don't keep it in memory; you do implicit operations in place when you're calculating elements of sparse matrix.
Fic Firic
2010-08-03 21:43:24