Matrix Multiplication and Binary Space Partitioning Trees : An Exploration

Abstract

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 $\Omega (D^{\tau })$ with radii less than $\arcsin (\epsilon /\sqrt{2})$ on the surface of the unit $D$-ball. The algorithm leverages a pruning rule necessary to guarantee $\epsilon$ 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.}