Matrix Multiplication in the MPC Model
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918150237323264 |
|---|---|
| author | Joshi, Lakshya Deshmukh, Arya Chhabra, Atharv Gupta, Chetan |
| author_facet | Joshi, Lakshya Deshmukh, Arya Chhabra, Atharv Gupta, Chetan |
| contents | In this paper, we present algorithms to solve matrix multiplication problems in the MPC model. In particular, we consider the problem under various processor/memory constraints in the MPC model and prove the following results.
1. Multiplication of two rectangular matrices of size $d \times n$ and $n \times d$ ( where $d \leq n$) respectively can be done in,
i) $O(\sqrt{d} + \log_d n)$ rounds with $n$ processors and $Θ(d)$ memory per processor
ii) $O(\frac{d}{\sqrt{n}})$ rounds with $d$ processors and $Θ(n)$ memory per processor.
2. Multiplication of two rectangular matrices of size $n \times d$ and $d \times n$ (where $d \leq n$) respectively, with $n$ processors of $Θ(n)$ memory per processor, can be done in $O(\frac{d}{\sqrt{n}})$ rounds.
3.The multiplication of two $d$-sparse matrices (matrices that contain at most $d$-nonzero elements in each row and in each column) with $n$ processors and $Θ(d)$ memory per processor can be done in $O(d^{0.9})$ rounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_19137 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Matrix Multiplication in the MPC Model Joshi, Lakshya Deshmukh, Arya Chhabra, Atharv Gupta, Chetan Computational Complexity Distributed, Parallel, and Cluster Computing In this paper, we present algorithms to solve matrix multiplication problems in the MPC model. In particular, we consider the problem under various processor/memory constraints in the MPC model and prove the following results. 1. Multiplication of two rectangular matrices of size $d \times n$ and $n \times d$ ( where $d \leq n$) respectively can be done in, i) $O(\sqrt{d} + \log_d n)$ rounds with $n$ processors and $Θ(d)$ memory per processor ii) $O(\frac{d}{\sqrt{n}})$ rounds with $d$ processors and $Θ(n)$ memory per processor. 2. Multiplication of two rectangular matrices of size $n \times d$ and $d \times n$ (where $d \leq n$) respectively, with $n$ processors of $Θ(n)$ memory per processor, can be done in $O(\frac{d}{\sqrt{n}})$ rounds. 3.The multiplication of two $d$-sparse matrices (matrices that contain at most $d$-nonzero elements in each row and in each column) with $n$ processors and $Θ(d)$ memory per processor can be done in $O(d^{0.9})$ rounds. |
| title | Matrix Multiplication in the MPC Model |
| topic | Computational Complexity Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2505.19137 |