Sparse matrix multiplication and triangle listing in the congested clique model (Q2290622): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q214794 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Dana Petcu / rank | |||
Normal rank |
Revision as of 22:08, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sparse matrix multiplication and triangle listing in the congested clique model |
scientific article |
Statements
Sparse matrix multiplication and triangle listing in the congested clique model (English)
0 references
29 January 2020
0 references
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.
0 references
distributed algorithms
0 references
congested clique
0 references
matrix multiplication
0 references
triangle listing
0 references