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

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.

arXiv commentI firmly believe that this is the right version