# An $O(n^2\log^4 n \log \log n)$ Time Matrix Multiplication Algorithm

Preprint · Yijie Han

- Archive id: arxiv:1612.04208
- Published: 2016-12-10
- arXiv: https://arxiv.org/abs/1612.04208
- Source URL: https://arxiv.org/abs/1612.04208
- PDF: https://arxiv.org/pdf/1612.04208
- Provenance: arxiv

## Abstract

We show, for the input vectors $(a\_0, a\_1, ..., a\_{n-1})$ and $(b\_0, b\_1, ..., b\_{n-1})$, where $a\_i$'s and $b\_j$'s are real numbers, after $O(n\\log^4 n)$ time preprocessing for each of them, the vector multiplication $(a\_0, a\_1, ..., a\_{n-1})(b\_0, b\_1, ..., b\_{n-1})^T $ can be computed in $O(\\log^4 n \\log \\log n)$ time. This enables the matrix multiplication for two $n\\times n$ matrices to be computed in $O(n^2 \\log^4 n\\log \\log n)$ time.

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