Projekteja vuodessa
Abstrakti
We study matrix multiplication in the lowbandwidth model: There are n computers, and we need to compute the product of two n × n matrices. Initially computer i knows row i of each input matrix. In one communication round each computer can send and receive one O(logn)bit message. Eventually computer i has to output row i of the product matrix. We seek to understand the complexity of this problem in the uniformly sparse case: each row and column of each input matrix has at most d nonzeros and in the product matrix we only need to know the values of at most d elements in each row or column. This is exactly the setting that we have, e.g., when we apply matrix multiplication for triangle detection in graphs of maximum degree d. We focus on the supported setting: the structure of the matrices is known in advance; only the numerical values of nonzero elements are unknown. There is a trivial algorithm that solves the problem in O(d2) rounds, but for a large d, better algorithms are known to exist; in the moderately dense regime the problem can be solved inO(dn1/3) communication rounds, and for very large d, the dominant solution is the fast matrix multiplication algorithm using O(n1.158) communication rounds (for matrix multiplication over fields and rings supporting fast matrix multiplication). In this work we show that it is possible to overcome quadratic barrier for all values of d: we present an algorithm that solves the problem in O(d1.907) rounds for fields and rings supporting fast matrix multiplication and O(d1.927) rounds for semirings, independent of n.
Alkuperäiskieli  Englanti 

Otsikko  SPAA 2022  Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures 
Kustantaja  ACM 
Sivut  435444 
Sivumäärä  10 
ISBN (elektroninen)  9781450391467 
DOI  pysyväislinkit  
Tila  Julkaistu  11 heinäk. 2022 
OKMjulkaisutyyppi  A4 Artikkeli konferenssijulkaisuussa 
Tapahtuma  Annual ACM Symposium on Parallelism in Algorithms and Architectures  Philadelphia, Yhdysvallat Kesto: 11 heinäk. 2022 → 14 heinäk. 2022 Konferenssinumero: 34 
Conference
Conference  Annual ACM Symposium on Parallelism in Algorithms and Architectures 

Lyhennettä  SPAA 
Maa/Alue  Yhdysvallat 
Kaupunki  Philadelphia 
Ajanjakso  11/07/2022 → 14/07/2022 
Sormenjälki
Sukella tutkimusaiheisiin 'Sparse Matrix Multiplication in the LowBandwidth Model'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.Projektit
 1 Päättynyt

: Rinnakkaisen ja hajautetun laskennan menetelmiä bayesilaisille graafisille malleille
Suomela, J., Vahidi, H., Hirvonen, J., Gupta, C. & Studeny, J.
04/09/2019 → 30/04/2023
Projekti: Academy of Finland: Other research funding