























We show that assuming the availability of the processor with variable precision arithmetic, we can compute matrix-by-matrix multiplications in $O(N^2log_2N)$ computational complexity. We replace the standard matrix-by-matrix multiplications $\begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22}\end{bmatrix}\begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22}\end{bmatrix}=\begin{bmatrix} 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{bmatrix}$ by $\begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22}\end{bmatrix}\begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22}\end{bmatrix}=\Bigl\lfloor\begin{bmatrix} (A_{11}+εA_{12})(B_{11}+1/εB_{21}) & (A_{11}+εA_{12})(B_{12}+1/εB_{22}) \\ (A_{21}+εA_{22})(B_{11}+1/εB_{21}) &(A_{21}+εA_{22})(B_{12}+1/εB_{22})\end{bmatrix} \Bigr\rfloor \% \frac{1}ε$ 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 $ε$ or $\frac{1}ε$, 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 $ε$ and $1/ε$) 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^2log_2N)$. 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 $(4log_2N+1)N^2$ vpa operations. This emulator uses $O(N)$ digits to run our algorithm.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。