# Matrix Multiplication in the MPC Model

Preprint · Lakshya Joshi, Arya Deshmukh, Atharv Chhabra, Chetan Gupta

- Archive id: arxiv:2505.19137
- Published: 2025-05-25
- arXiv: https://arxiv.org/abs/2505.19137
- Source URL: https://arxiv.org/abs/2505.19137
- PDF: https://arxiv.org/pdf/2505.19137
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.