On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems

doi:10.1007/s42967-023-00358-7

Communications on Applied Mathematics and Computation ›› 2025, Vol. 7 ›› Issue (4): 1580-1597.doi: 10.1007/s42967-023-00358-7

• ORIGINAL PAPERS • 上一篇下一篇

On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems

Long-Ze Tan¹, Ming-Yu Deng², Xue-Ping Guo¹

1. Key Laboratory of MEA (Ministry of Education) & Shanghai Key Laboratory of PMMP, School of Mathematical Sciences, East China Normal University, Shanghai, 200241, China;
2. School of International Trade and Economics, University of International Business and Economics, Beijing, 100029, China

收稿日期:2022-11-20 修回日期:2023-12-01 接受日期:2023-12-03 出版日期:2024-03-25 发布日期:2024-03-25
通讯作者: Xue-Ping Guo,E-mail:xpguo@math.ecnu.edu.cn E-mail:xpguo@math.ecnu.edu.cn
作者简介:Long-Ze Tan, E-mail:51205500081@stu.ecnu.edu.cn;Ming-Yu Deng, E-mail:my_deng@stu.ecnu.edu.cn
基金资助:
This work is partly supported by the National Natural Science Foundation of China (No. 12071149), the Science and Technology Commission of Shanghai Municipality of China (No. 22DZ2229014), and the National Key R &D Program of China (No. 2022YFA1004403).

On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems

Long-Ze Tan¹, Ming-Yu Deng², Xue-Ping Guo¹

1. Key Laboratory of MEA (Ministry of Education) & Shanghai Key Laboratory of PMMP, School of Mathematical Sciences, East China Normal University, Shanghai, 200241, China;
2. School of International Trade and Economics, University of International Business and Economics, Beijing, 100029, China

Received:2022-11-20 Revised:2023-12-01 Accepted:2023-12-03 Online:2024-03-25 Published:2024-03-25
Supported by:
This work is partly supported by the National Natural Science Foundation of China (No. 12071149), the Science and Technology Commission of Shanghai Municipality of China (No. 22DZ2229014), and the National Key R &D Program of China (No. 2022YFA1004403).

摘要/Abstract

摘要： Based on the greedy randomized Kaczmarz (GRK) method, we propose a multi-step greedy Kaczmarz method for solving large-scale consistent linear systems, utilizing multi-step projection techniques. Its convergence is proved when the linear system is consistent. Numerical experiments demonstrate that the proposed method is effective and more efficient than several existing classical Kaczmarz methods.

关键词: System of linear equations, Kaczmarz method, Greedy randomized Kaczmarz (GRK) method, Multi-step greedy Kaczmarz method, Convergence

Abstract: Based on the greedy randomized Kaczmarz (GRK) method, we propose a multi-step greedy Kaczmarz method for solving large-scale consistent linear systems, utilizing multi-step projection techniques. Its convergence is proved when the linear system is consistent. Numerical experiments demonstrate that the proposed method is effective and more efficient than several existing classical Kaczmarz methods.

Key words: System of linear equations, Kaczmarz method, Greedy randomized Kaczmarz (GRK) method, Multi-step greedy Kaczmarz method, Convergence

中图分类号:

Long-Ze Tan, Ming-Yu Deng, Xue-Ping Guo. On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1580-1597.

参考文献

[1] Ansorge, R.: Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations. Computing 33(3), 367-375 (1984)
[2] Bai, Z.-Z., Jin, C.-H.: Column-decomposed relaxation methods for the overdetermined systems of linear equations. Int. J. Appl. Math. 13(1), 71-82 (2003)
[3] Bai, Z.-Z., Liu, X.-G.: On the Meany inequality with applications to convergence analysis of several row-action iteration methods. Numer. Math. 124(2), 215-236 (2013)
[4] Bai, Z.-Z., RozloznÍk, M.: On the numerical behavior of matrix splitting iteration methods for solving linear systems. SIAM J. Numer. Anal. 53(4), 1716-1737 (2015)
[5] Bai, Z.-Z., Wang, L.: On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems. Appl. Numer. Math. 192, 197-213 (2023)
[6] Bai, Z.-Z., Wang, L.: On convergence rates of Kaczmarz-type methods with different selection rules of working rows. Appl. Numer. Math. 186, 289-319 (2023)
[7] Bai, Z.-Z., Wu, W.-T.: On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput. 40(1), A592-A606 (2018)
[8] Bai, Z.-Z., Wu, W.-T.: On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems. Appl. Math. Lett. 83, 21-26 (2018)
[9] Bai, Z.-Z., Wu, W.-T.: On convergence rate of the randomized Kaczmarz method. Linear Algebra Appl. 553, 252-269 (2018)
[10] Bai, Z.-Z., Wu, W.-T.: On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems. Linear Algebra Appl. 578, 225-250 (2019)
[11] Bai, Z.-Z., Wu, W.-T.: On greedy randomized coordinate descent methods for solving large linear least-squares problems. Numer. Linear Algebra Appl. 26(4), 1-15 (2019)
[12] Bai, Z.-Z., Wu, W.-T.: Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory. Jpn. J. Ind. Appl. Math. 40, 1-23 (2023)
[13] Brezinski, C.: Projection Methods for Systems of Equations. Elsevier Science, Amsterdam (1997)
[14] Byrne, C.: A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl. 20(1), 103-120 (2003)
[15] Byrne, C.L.: Applied Iterative Methods. A.K. Peters, Wellesley (2007)
[16] Censor, Y.: Row-action methods for huge and sparse systems and their applications. SIAM Rev. 23(4), 444-466 (1981)
[17] Censor, Y.: Parallel application of block-iterative methods in medical imaging and radiation therapy. Math. Program. 42(1), 307-325 (1988)
[18] Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1-25 (2011)
[19] Du, K., Gao, H.: A new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm. Numer. Math. Theory Methods Appl. 12(2), 627-639 (2019)
[20] Eggermont, P.P.B., Herman, G.T., Lent, A.: Iterative algorithms for large partitioned linear systems, with applications to image reconstruction. Linear Algebra Appl. 40, 37-67 (1981)
[21] Elble, J.M., Sahinidis, N.V., Vouzis, P.: GPU computing with Kaczmarz’s and other iterative algorithms for linear systems. Parallel Comput. 36, 215-231 (2010)
[22] Galántai, A.: Projectors and Projection Methods. Kluwer Academic Publishers, Norwell (2004)
[23] Gower, R.M., Richtárik, P.: Stochastic dual ascent for solving linear systems. https://arxiv.org/abs/1512.06890 (2015)
[24] Herman, G.T., Davidi, R.: Image reconstruction from a small number of projections. Inverse Probl. 24(4), 1-18 (2008)
[25] Herman, G.T., Meyer, L.B.: Algebraic reconstruction techniques can be made computationally efficient (positron emission tomography application). IEEE Trans. Med. Imaging 12, 600-609 (1993)
[26] Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Int. Acad. Polon. Sci. Lett. A 35, 355-357 (1937)
[27] Knight, P.A.: Error Analysis of Stationary Iteration and Associated Problems. Ph. D. thesis, Manchester University, Manchester (1993)
[28] Leventhal, D., Lewis, A.S.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35, 641-654 (2010)
[29] Lorenz, D.A., Wenger, S., Schöpfer, F., Magnor, M.: A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing. In: 2014 IEEE International Conference on Image Processing (ICIP), Paris, France, 1347-1351 (2014)
[30] Ma, A., Needell, D., Ramdas, A.: Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. SIAM J. Matrix Anal. Appl. 36, 1590-1604 (2015)
[31] McCormick, S.F.: The methods of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in Hilbert space. Indiana Univ. Math. J. 26, 1137-1150 (1977)
[32] Natterer, F.: The Mathematics of Computerized Tomography. SIAM, Philadelphia (2001)
[33] Needell, D.: Randomized Kaczmarz solver for noisy linear systems. BIT Numer. Math. 50, 395-403 (2010)
[34] Needell, D., Tropp, J.A.: Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra Appl. 441, 199-221 (2014)
[35] Pasqualetti, F., Carli, R., Bullo, F.: Distributed estimation via iterative projections with application to power network monitoring. Automatica J. IFAC 48, 747-758 (2012)
[36] Popa, C., Zdunek, R.: Kaczmarz extended algorithm for tomographic image reconstruction from limited-data. Math. Comput. Simul. 65, 579-598 (2004)
[37] Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262-278 (2009)
[38] Tan, L.-Z., Guo, X.-P.: On multi-step greedy randomized coordinate descent method for solving large linear least-squares problems. Comput. Appl. Math. 42(37), 1-20 (2023)
[39] Zhang, J.-J.: A new greedy Kaczmarz algorithm for the solution of very large linear systems. Appl. Math. Lett. 91, 207-212 (2019)
[40] Zhang, J.-J., Guo, J.-H.: On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems. Appl. Numer. Math. 157, 372-384 (2020)
[41] Zhang, K., Li, F.-T., Jiang, X.-L.: Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems. Comput. Appl. Math. 41(332), 1-25 (2022)
[42] Zouzias, A., Freris, N.M.: Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. 34, 773-793 (2013)

On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems

On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	Zhao-Zheng Liang, Jun-Lin Tian, Hong-Yi Wan. A Note on Chebyshev Accelerated PMHSS Iteration Method for Block Two-by-Two Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1242-1263.
[2]	Huaijun Yang. Unconditionally Superconvergence Error Analysis of an Energy-Stable and Linearized Galerkin Finite Element Method for Nonlinear Wave Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1264-1281.
[3]	Lu-Xin Wang, Qin-Qin Shen, Yang Cao. Modulus-Based Matrix Splitting Iteration Method for Horizontal Quasi-complementarity Problem[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1308-1332.
[4]	Xing Liu. An Accelerated Convergence Scheme for Solving Stochastic Fractional Diffusion Equation[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1444-1461.
[5]	Jing Chen, Qi Wang. Numerical Stability and Convergence for Delay Space-Fractional Fisher Equations with Mixed Boundary Conditions in Two Dimensions[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1462-1488.
[6]	Xuan Zhao, Zhongqin Xue. Efficient Variable Steps BDF2 Scheme for the Two-Dimensional Space Fractional Cahn-Hilliard Model[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1489-1515.
[7]	Yujian Cao, Jianguo Huang, Haoqin Wang. A Hybrid Iterative Method for Elliptic Variational Inequalities of the Second Kind[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 910-928.
[8]	Yun-Xia Tan, Zheng-Da Huang. On a Nonlinear Fast Deterministic Block Kaczmarz Method for Solving Nonlinear Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 954-969.
[9]	Gang Bao, Peijun Li, Xiaokai Yuan. Convergence of the PML Method for the Biharmonic Wave Scattering Problem in Periodic Structures[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 1122-1145.
[10]	Shipeng Mao, Jiaao Sun. Error Estimates of Finite Element Method for the Incompressible Ferrohydrodynamics Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 485-535.
[11]	Gui-Lin Yan, Yu-Jiang Wu, Bo Deng. Improvement of Convergence of One- and Two-Step MSM Iteration Methods for Nondifferentiable Nonlinear Complementarity Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 733-758.
[12]	Mengfei Wang, Yan Xu. Superconvergence of UWLDG Method for One-Dimensional Linear Sixth-Order Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 771-795.
[13]	Ren Liu, Lifei Wu. Numerical Approach for Solving Two-Dimensional Time-Fractional Fisher Equation via HABC-N Method[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 315-346.
[14]	Pavel Bakhvalov, Mikhail Surnachev. On the Order of Accuracy of Edge-Based Schemes: a Peterson-Type Counter-Example[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 372-391.
[15]	Jieying Zhang, Caixia Ou, Zhibo Wang, Seakweng Vong. An Order Reduction Method for the Nonlinear Caputo-Hadamard Fractional Diffusion-Wave Model[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 392-408.