# Matrix Multiplication and Binary Space Partitioning Trees : An Exploration

Preprint · CNP Slagle, Lance Fortnow

- Archive id: arxiv:2012.05365
- Published: 2020-12-09
- arXiv: https://arxiv.org/abs/2012.05365
- Source URL: https://arxiv.org/abs/2012.05365
- PDF: https://arxiv.org/pdf/2012.05365
- Provenance: arxiv

## 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 $Ω(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.}

_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.