矩阵乘法“正则化-滤波-重采样”快速算法

doi:10.3969/j.issn.0255-8297.2026.02.009

应用科学学报 ›› 2026, Vol. 44 ›› Issue (2): 297-315.doi: 10.3969/j.issn.0255-8297.2026.02.009

矩阵乘法“正则化-滤波-重采样”快速算法

丁广太, 刘通, 支小莉, 武频, 童维勤

上海大学计算机工程与科学学院, 上海 200444

收稿日期:2026-01-10 发布日期:2026-04-07
通信作者: 丁广太，副教授，研究方向为矩阵计算、图像分析和机器学习。E-mail:gtding@shu.edu.cn E-mail:gtding@shu.edu.cn
基金资助:
空天飞行空气动力科学与技术全国重点实验室开放课题（No.SKLA-2024-FKFT-3-005）；上海市专业技术服务平台建设项目（No.20DZ2294000）；上海市科委地方院校能力建设专项（No.23010500400）

A Fast Algorithm for Matrix Multiplication Based on “Regularization-Filtering-Resampling”

DING Guangtai, LIU Tong, ZHI Xiaoli, WU Pin, TONG Weiqin

School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China

Received:2026-01-10 Published:2026-04-07

摘要/Abstract

摘要： 聚焦大矩阵乘法的精确算法、近似算法在速度、精度和效率方面的优势折衷问题，提出一种基于正则化、滤波、重采样技术的面向稠密矩阵乘法快速算法。基于采样定理，建立矩阵与其对应的模拟函数之间的正则化关系，进而引入滤波、重采样环节，实现精确算法和近似算法的折衷机制。为追求较高的综合效率，研究了该算法的适用范围和条件，尤其是算法精度与矩阵元素数据统计特性的关系。采用独立同分布随机数发生器等方法生成的矩阵进行了数据实验，表明算法能够实现折衷目标。

关键词: 矩阵乘法, 快速算法, 采样定理, 正则化

Abstract: 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.

Key words: matrix multiplication, fast algorithm, sampling theorem, regularization

中图分类号:

O241.6

丁广太, 刘通, 支小莉, 武频, 童维勤. 矩阵乘法“正则化-滤波-重采样”快速算法[J]. 应用科学学报, 2026, 44(2): 297-315.

DING Guangtai, LIU Tong, ZHI Xiaoli, WU Pin, TONG Weiqin. A Fast Algorithm for Matrix Multiplication Based on “Regularization-Filtering-Resampling”[J]. Journal of Applied Sciences, 2026, 44(2): 297-315.

参考文献

[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.

矩阵乘法“正则化-滤波-重采样”快速算法

A Fast Algorithm for Matrix Multiplication Based on “Regularization-Filtering-Resampling”

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价

[1]	韩佳洁, 苑清扬, 张博, 赵鑫, 兰天, 李郁. 基于少测点噪声数据重构问题的改进Gappy POD算法[J]. 应用科学学报, 2025, 43(5): 740-756.
[2]	孙物一, 冯国瑞. 基于高维特征正则化的JPEG图像隐写分析[J]. 应用科学学报, 2016, 34(5): 555-563.
[3]	沈璇, 赵光耀, 李超, 李瑞林. MD5加密模式的差分故障分析[J]. 应用科学学报, 2015, 33(5): 481-490.
[4]	张建军;王芹. 二值图像恢复的一个非线性正则化方法（英）[J]. 应用科学学报, 2009, 27(1): 74-78 .
[5]	韩玉兵, 吴乐南. 基于PDE演化的视频图像序列超分辨率重建[J]. 应用科学学报, 2005, 23(4): 331-335.
[6]	韩玉兵, 吴乐南. 基于改进Paik型Hopfield网络的图像复原[J]. 应用科学学报, 2005, 23(2): 126-130.
[7]	童创明, 袁乃昌, 付云起, 张国华. FSS电磁散射方向特性的快速计算[J]. 应用科学学报, 2003, 21(1): 103-106.
[8]	彭仲秋. 二维电磁逆散射变形玻恩迭代法的改进[J]. 应用科学学报, 1993, 11(4): 297-302.