Matrix-by-matrix multiplication algorithm with $O(N^{2}lo{g}_{2}N)$ computational complexity for variable precision arithmetic

Abstract

We show that assuming the availability of the processor with variable precision arithmetic, we can compute matrix-by-matrix multiplications in $O(N^{2}lo{g}_{2}N)$ computational complexity. We replace the standard matrix-by-matrix multiplications $\left[\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right]\left[\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right]=\left[\begin{array}{cc}{A}_{11}{B}_{11}+A_{12}{B}_{21}& A_{11}{B}_{12}+A_{12}{B}_{22}\\ A_{21}{B}_{11}+A_{22}{B}_{21}& A_{21}{B}_{12}+A_{22}{B}_{22}\end{array}\right]$ by $\left[\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right]\left[\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right]=\lfloor \left[\begin{array}{cc}(A_{11}+\hat{I}\mu A_{12})(B_{11}+1/\hat{I}\mu B_{21})& (A_{11}+\hat{I}\mu A_{12})(B_{12}+1/\hat{I}\mu B_{22})\\ (A_{21}+\hat{I}\mu A_{22})(B_{11}+1/\hat{I}\mu B_{21})& (A_{21}+\hat{I}\mu A_{22})(B_{12}+1/\hat{I}\mu B_{22})\end{array}\right]\rfloor \%\frac{1}{\hat{I}}\mu$ where $\lfloor \rfloor$ denotes the floor, and $\%$ denotes the modulo operators. We reduce the number of block matrix-by-matrix multiplications from 8 to 4, keeping the number of additions equal to 4, and additionally introducing 4 multiplications of a block matrices by $\hat{I}\mu$ or $\frac{1}{\hat{I}}\mu$, and 4 floor and 4 modulo operations. The resulting computational complexity for two matrices of size $N\times N$ can be estimated from recursive equation $T(N)=4(N/2{)}^2$ (multiplication of a matrix by $\hat{I}\mu$ and $1/\hat{I}\mu$) plus $4(N/2{)}^2$ (additions of two matrices) plus $2N^2$ (floor and modulo) plus $4T(N/2)$ (four recursive calls) as $O(N^{2}lo{g}_{2}N)$. These multiplications of blocks of a matrix by number scales like $O((N/2{)}^2)$. We also present a MATLAB code using \emph{vpa} variable precision arithmetic emulator that can multiply matrices of size $N\times N$ using $(4lo{g}_{2}N+1)N^2$ vpa operations. This emulator uses $O(N)$ digits to run our algorithm.

20 pages, 2 tables, 1 figure