标题： 矩阵乘法在MPC模型中 显示英文标题

标题： Matrix Multiplication in the MPC Model

摘要： 在本文中，我们提出了算法来解决MPC模型中的矩阵乘法问题。 特别地，我们在MPC模型下的各种处理器/内存约束条件下考虑了该问题，并证明了以下结果。 1. 两个大小分别为$d \times n$和$n \times d$（其中$d \leq n$）的矩形矩阵相乘可以在， i)$O(\sqrt{d} + \log_d n)$轮次中使用$n$处理器和每个处理器$\Theta(d)$的内存 ii)$O(\frac{d}{\sqrt{n}})$轮次中使用$d$处理器和每个处理器$\Theta(n)$的内存 2. 大小分别为$n \times d$和$d \times n$的两个矩形矩阵（其中$d \leq n$）的乘法，使用每个处理器有$\Theta(n)$内存的$n$个处理器，可以在$O(\frac{d}{\sqrt{n}})$轮中完成。 3.两个$d$-稀疏矩阵（每行和每列最多包含$d$个非零元素的矩阵）在$n$个处理器和每个处理器$\Theta(d)$内存的情况下，可以在$O(d^{0.9})$轮中完成乘法运算。 显示英文摘要

摘要： 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 $\Theta(d)$ memory per processor ii) $O(\frac{d}{\sqrt{n}})$ rounds with $d$ processors and $\Theta(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 $\Theta(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 $\Theta(d)$ memory per processor can be done in $O(d^{0.9})$ rounds.