Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911108148756480 |
|---|---|
| author | Paszyński, Maciej |
| author_facet | Paszyński, Maciej |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21050 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic Paszyński, Maciej Data Structures and Algorithms Computational Complexity Mathematical Software 68 F.2.1; G.4 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. |
| title | Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic |
| topic | Data Structures and Algorithms Computational Complexity Mathematical Software 68 F.2.1; G.4 |
| url | https://arxiv.org/abs/2410.21050 |