2024/10/28 by Maciej Paszyński, Paszyński, Maciej
Computer Science · #68 #Computational Complexity (cs.CC) #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #G.4 #Mathematical Software (cs.MS) #Numerical Methods and Algorithms #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2410.21050
openalex publication_date 2024/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that assuming the availability of the processor with variable precision arithmetic, we can compute matrix-by-matrix multiplications in O(N2log2N) computational complexity. We replace the standard matrix-by-matrix multiplications \beginbmatrix A11 & A12 A21 & A22\endbmatrix\beginbmatrix B11 & B12 B21 & B22\endbmatrix=\beginbmatrix A11B11+A12B21 & A11B12+A12B22 A21B11+A22B21 & A21B12+A22B22\endbmatrix by \beginbmatrix A11 & A12 A21 & A22\endbmatrix\beginbmatrix B11 & B12 B21 & B22\endbmatrix=\lfloor\beginbmatrix (A11+εA12)(B11+1/εB21) & (A11+εA12)(B12+1/εB22) (A21+εA22)(B11+1/εB21) &(A21+εA22)(B12+1/εB22)\endbmatrix \rfloor % \frac1ε 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 \frac1ε, and 4 floor and 4 modulo operations. The resulting computational complexity for two matrices of size N× 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 2N2 (floor and modulo) plus 4T(N/2) (four recursive calls) as O(N2log2N). These multiplications of blocks of a matrix by number scales like O((N/2)2). We also present a MATLAB code using vpa variable precision arithmetic emulator that can multiply matrices of size N× N using (4log2N+1)N2 vpa operations. This emulator uses O(N) digits to run our algorithm.