Sparse matrix multiplication and triangle listing in the congested clique model (Q2290622): Difference between revisions

The paper deals with the problem of multiplying sparse matrices. For the parallel setting the distributed Congested Clique model, which consists of nodes in a fully connected synchronous network, is used. A new deterministic algorithm with a round complexity which depends on the sparsity of the input matrices is proposed. A special characteristic of the algorithm is that it speeds up matrix multiplication even if only one of the input matrices is sparse. The approach is extended to obtain a deterministic algorithm for sparsity-aware triangle listing in the Congested Clique model, in which each triangle needs to be known to some node.