论文标题
矩阵乘法和二进制空间划分树：探索
Matrix Multiplication and Binary Space Partitioning Trees : An Exploration
论文作者
论文摘要
本文中，我们探索了$ a \ in \ mathbb {r}^{m \ times d} $的矩阵乘法的双树算法和$ b \ in \ mathbb {r}^{r}^{d \ times n} $ $ \ mathbb {r}^{d} $，属于与$ω（d^τ）$成比例的radii，小于$ \ arcsin（ε/\ sqrt {2}）$在单位$ d $ ball的表面上。该算法利用了确保与所得矩阵中矢量幅度量产物相称的$ε$精度所需的修剪规则。 \ textIt {不幸的是，如果行和列均匀分布在单元$ d $ - 鲍尔的表面，则每个必需群集的预期点在$ d $中呈端快速接近零；因此，该方法需要大量工作才能通过召集。}
Herein we explore a dual tree algorithm for matrix multiplication of $A\in \mathbb{R}^{M\times D}$ and $B\in\mathbb{R}^{D\times N}$, very narrowly effective if the normalized rows of $A$ and columns of $B$, treated as vectors in $\mathbb{R}^{D}$, fall into clusters of order proportionate to $Ω(D^τ)$ with radii less than $\arcsin(ε/\sqrt{2})$ on the surface of the unit $D$-ball. The algorithm leverages a pruning rule necessary to guarantee $ε$ precision proportionate to vector magnitude products in the resultant matrix. \textit{ Unfortunately, if the rows and columns are uniformly distributed on the surface of the unit $D$-ball, then the expected points per required cluster approaches zero exponentially fast in $D$; thus, the approach requires a great deal of work to pass muster.}
