聚焦大矩阵乘法的精确算法、近似算法在速度、精度和效率方面的优势折衷问题，提出一种基于正则化、滤波、重采样技术的面向稠密矩阵乘法快速算法。基于采样定理，建立矩阵与其对应的模拟函数之间的正则化关系，进而引入滤波、重采样环节，实现精确算法和近似算法的折衷机制。为追求较高的综合效率，研究了该算法的适用范围和条件，尤其是算法精度与矩阵元素数据统计特性的关系。采用独立同分布随机数发生器等方法生成的矩阵进行了数据实验，表明算法能够实现折衷目标。
Focusing on the trade-off in terms of speed, accuracy and efficiency between the exact and approximate algorithms for large-scale matrix multiplication, this paper proposed a fast algorithm for dense matrix multiplication employing regularization, filtering, and resampling techniques. Based on the sampling theorem, a regularization relationship between the matrix and its corresponding analog function was established, and then filtering and resampling stages were introduced to achieve the trade-off mechanism between the exact algorithm and the approximate algorithm. In pursuit of higher algorithmic efficiency, the applicable scope and conditions of the algorithm were investigated, especially the relationship between the algorithm accuracy and the statistical characteristics of the matrix data. Data experiments were conducted using matrices generated by methods such as independent and identically distributed random number generators. The results indicate that the algorithm achieves its trade-off objectives.
[1] Strassen V. Gaussian elimination is not optimal [J]. Numerische Mathematik, 1969, 13(4): 354-356.
[2] Afroz S, Tahaseen M, Ahmeo F, et al. Survey on matrix multiplication algorithms [C]//5th International Conference on Informatics, Electronics and Vision (ICIEV), 2016: 151-155.
[3] Gao J H, Ji W X, Chang F L, et al. A systematic survey of general sparse matrix-matrix multiplication [J]. ACM CSUR, 2023, 55(12): 1-36.
[4] Pan V Y. Fast matrix multiplication and its algebraic neighbourhood [J]. Sbornik: Mathematics, 2017, 208(11): 1661-1704.
[5] Williams V V. Multiplying matrices faster than Coppersmith-Winograd [C]//44th Annual ACM Symposium on Theory of Computing, 2012: 887-898.
[6] Alman J, Duan R, Williams V V, et al. More asymmetry yields faster matrix multiplication [C]//Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025: 2005-2039.
[7] 刘丽, 陈长波. 带状稀疏矩阵乘法及高效GPU实现[J]. 计算机应用, 2023, 43(12): 3856-3867. Liu L, Chen C B. Band sparse matrix multiplication and efficient GPU implementation [J]. Journal of Computer Applications, 2023, 43(12): 3856-3867. (in Chinese)
[8] Gong S, Qian S, Zhao C, et al. Accelerating DNN-based detection by MADDNESS approximation [C]//IEEE Vehicular Technology Conference, 2024: 1-6.
[9] Drineas P, Kannan R, Mahoney M W. Fast monte carlo algorithms for matrices Ⅰ : approximating matrix multiplication [J]. SIAM journal on computing, 2006, 36(1): 132-157.
[10] Korec I, Wiedermann J. Deterministic verification of integer matrix multiplication in quadratic time [M]. Cham: Springer International Publishing, 2014. 375–382.
[11] Yang C, Musco C. Efficient block approximate matrix multiplication [C]//31st Annual European Symposium on Algorithms, 2023: 274.
[12] Niu C, Li H. Optimal sampling algorithms for block matrix multiplication [J]. Journal of computational and applied mathematics, 2023, 425: 115063.
[13] Francis D P, Raimond K. A practical streaming approximate matrix multiplication algorithm [J]. Journal of King Saud University, Computer and information sciences, 2022, 34(1): 1455-1465.
[14] Wu Y. A note on random sampling for matrix multiplication [DB/OL]. (2019-05-16) [2025-12- 30]. https://arxiv.org/abs/1811.11237.
[15] Iwen M A, Spencer C V. A note on compressed sensing and the complexity of matrix multiplication [J]. Information Processing Letters, 2029, 109(10): 468-471.
[16] Mishra I, Jain S. A performance analysis of measurement matrices used in compressed sensing techniques [J]. Turkish Journal of Computer and Mathematics Education, 2021, 12(13): 1383- 1392.
[17] Dai L, Cheng X, Wang B, et al. Application of matrix multiplication in signal sensor image perception [J]. Applied mathematics and nonlinear sciences, 2023, 8(2): 601-614.
[18] Jia Y, Guo H, Guo Y, et al. An efficient optical sparse matrix multiplication accelerator for graph neural networks [C]//Asia Communications and Photonics Conference (ACP), 2022: 1868-1872.
[19] Andras P. High-dimensional function approximation with neural networks for large volumes of data [J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(2): 500-508.
[20] Dehghankar M, Erfanian M, Asudeh A. An efficient matrix multiplication algorithm for accelerating inference in binary and ternary neural networks [C]//42nd International Conference on Machine Learning, 2025: 12969-12986.
[21] Xu Y, Shi H, Wang Z. NASH: neural architecture and accelerator search for multiplicationreduced hybrid models [DB/OL]. (2024-09-07) [2025-12-10]. https://arxiv.org/abs/2409.04829.
[22] Christandl M, Vrana P, Zuiddam J. Barriers for fast matrix multiplication from irreversibility [C]//34th Computational Complexity Conference, 2019: 1-17.
[23] 张贤达. 矩阵分析与应用[M]. 2版. 北京: 清华大学出版社, 2013.
[24] 宋耀良, 穆童. 从广义采样、 小波到压缩感知[J]. 数据采集与处理, 2016, 30(4): 665–674. Song Y L, Mu T. From generalized sampling and wavelet to compressed sensing [J]. Journal of Data Acquisition and Processing, 2016, 30(4): 665-674. (in Chinese)
[25] 杨福生. 小波变换的工程分析与应用[M]. 北京: 科学出版社, 1999.
[26] 徐树方, 钱江. 矩阵计算六讲[M]. 北京: 高等教育出版社, 2011.
[27] Higham N J. Cholesky factorization [J]. WIREs. Computational Statistics, 2009, 1(2): 251-254.
[28] Shams Solary M. A review for finding determinants of some band matrices [J]. Soft Computing, 2025, 29: 3073-3082.
