An efficient variant of the greedy block Kaczmarz algorithm for solving large linear systems

Ke Zhang; Hong-Yan Yin; Xiang-Long Jiang; Ke Zhang; Hong-Yan Yin; Xiang-Long Jiang

doi:10.3934/math.2024122

AIMS Mathematics

2024, Volume 9, Issue 1: 2473-2499. doi: 10.3934/math.2024122

Previous Article Next Article

Research article

An efficient variant of the greedy block Kaczmarz algorithm for solving large linear systems

Department of Mathematics, Shanghai Maritime University, Shanghai 201306, China

Received: 06 November 2023 Revised: 11 December 2023 Accepted: 19 December 2023 Published: 25 December 2023
MSC : 65F10, 65F20, 15A06

By exploiting the concept of row partitioning, we propose an efficient variant of the greedy block Kaczmarz algorithm for solving consistent large linear systems. The number of blocks is determined a priori through numerical experiments. The new algorithm works with a reduced linear system, which dramatically diminishes the computational overhead per iteration. The theoretical result validates that this method converges to the unique least-norm solution of the linear system. The effectiveness of the proposed algorithm is also justified by comparing it with some block Kaczmarz algorithms in extensive numerical experiments.
- linear system,
- Kaczmarz method,
- greedy Kaczmarz method,
- block Kaczmarz method
Citation: Ke Zhang, Hong-Yan Yin, Xiang-Long Jiang. An efficient variant of the greedy block Kaczmarz algorithm for solving large linear systems[J]. AIMS Mathematics, 2024, 9(1): 2473-2499. doi: 10.3934/math.2024122

Related Papers:

Abstract

By exploiting the concept of row partitioning, we propose an efficient variant of the greedy block Kaczmarz algorithm for solving consistent large linear systems. The number of blocks is determined a priori through numerical experiments. The new algorithm works with a reduced linear system, which dramatically diminishes the computational overhead per iteration. The theoretical result validates that this method converges to the unique least-norm solution of the linear system. The effectiveness of the proposed algorithm is also justified by comparing it with some block Kaczmarz algorithms in extensive numerical experiments.

References

[1]	A. Agaskar, C. Wang, Y. M. Lu, Randomized Kaczmarz algorithms: Exact MSE analysis and optimal sampling probabilities, 2014 IEEE Global Conference on Signal and Information Processing (Global-SIP), 389–393. https://doi.org/10.1109/GlobalSIP.2014.7032145
[2]	Z. Z. Bai, X. G. Liu, On the Meany inequality with applications to convergence analysis of several row-action iteration methods, Numer. Math., 124 (2013), 215–236. https://doi.org/10.1007/s00211-012-0512-6 doi: 10.1007/s00211-012-0512-6
[3]	Z. Z. Bai, L. Wang, On convergence rates of Kaczmarz-type methods with different selection rules of working rows, Appl. Numer. Math., 186 (2023), 289–319. https://doi.org/10.1016/j.apnum.2023.01.013 doi: 10.1016/j.apnum.2023.01.013
[4]	Z. Z. Bai, W. T. Wu, On convergence rate of the randomized Kaczmarz method, Linear Algebra Appl., 553 (2018), 252–269. https://doi.org/10.1016/j.laa.2018.05.009 doi: 10.1016/j.laa.2018.05.009
[5]	Z. Z. Bai, W. T. Wu, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606. https://doi.org/10.1137/17M1137747 doi: 10.1137/17M1137747
[6]	Z. Z. Bai, W. T. Wu, On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Appl. Math. Lett., 83 (2018), 21–26. https://doi.org/10.1016/j.aml.2018.03.008 doi: 10.1016/j.aml.2018.03.008
[7]	Z. Z. Bai, W. T. Wu, Randomized Kaczmarz iteration methods: Algorithmic extensions and convergence theory, Jpn. J. Ind. Appl. Math., 40 (2023), 1421–1443. https://doi.org/10.1007/s13160-023-00586-7 doi: 10.1007/s13160-023-00586-7
[8]	E. Bodewig, Bericht über die verschiedenen Methoden zur Lösung eines System linearer Gleichungen mit reellen Koeffizienten, Cons. Naz. Ric., 324 (1948), 441–452.
[9]	C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl., 20 (2004), 103–120. https://doi.org/10.1088/0266-5611/20/1/006 doi: 10.1088/0266-5611/20/1/006
[10]	J. Q. Chen, Z. D. Huang, On a fast deterministic block Kaczmarz method for solving large-scale linear systems, Numer. Algorithms, 89 (2022), 1007–1029. https://doi.org/10.1007/s11075-021-01143-4 doi: 10.1007/s11075-021-01143-4
[11]	T. A. Davis, Y. Hu, The university of Florida sparse matrix collection, ACM T. Math. Software, 38 (2011), 1–25. https://doi.org/10.1145/2049662.2049663 doi: 10.1145/2049662.2049663
[12]	K. Du, W. T. Si, X. H. Sun, Randomized extended average block Kaczmarz for solving least squares, SIAM J. Sci. Comput., 42 (2020), A3541–A3559. https://doi.org/10.1137/20M1312629 doi: 10.1137/20M1312629
[13]	Y. C. Eldar, D. Needell, Acceleration of randomized Kaczmarz methods via the Johnson-Lindenstrauss lemma, Numer. Algorithms, 58 (2011), 163–177. https://doi.org/10.1007/s11075-011-9451-z doi: 10.1007/s11075-011-9451-z
[14]	T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numer. Math., 35 (1980), 1–12. https://doi.org/10.1007/BF01396365 doi: 10.1007/BF01396365
[15]	G. E. Forsythe, Solving linear algebraic equations can be interesting, Bull. Amer. Math. Soc., 59 (1953), 299–329.
[16]	R. Gordon, R. Bender, G. T. Herman, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and $X$-ray photography, J. Theoret. Biol., 29 (1970), 471–481. https://doi.org/10.1016/0022-5193(70)90109-8 doi: 10.1016/0022-5193(70)90109-8
[17]	R. M. Gower, D. Molitor, J. Moorman, D. Needell, On adaptive sketch-and-project for solving linear systems, SIAM J. Matrix Anal. A., 42 (2021), 954–989. https://doi.org/10.1137/19M1285846 doi: 10.1137/19M1285846
[18]	R. M. Gower, P. Richtárik, Randomized iterative methods for linear systems, SIAM J. Matrix Anal. A., 36 (2015), 1660–1690. https://doi.org/10.1137/15M1025487 doi: 10.1137/15M1025487
[19]	M. Griebel, P. Oswald, Greedy and randomized versions of the multiplicative Schwarz method, Linear Algebra Appl., 437 (2012), 1596–1610. https://doi.org/10.1016/j.laa.2012.04.052 doi: 10.1016/j.laa.2012.04.052
[20]	G. T. Herman, Fundamentals of computerized tomography: Image reconstruction from projections, 2 Eds., Springer, Dordrecht, 2009. https://doi.org/10.1007/978-1-84628-723-7
[21]	X. L. Jiang, K. Zhang, J. F. Yin, Randomized block Kaczmarz methods with $k$-means clustering for solving large linear systems, J. Comput. Appl. Math., 403 (2022), 113828. https://doi.org/10.1016/j.cam.2021.113828 doi: 10.1016/j.cam.2021.113828
[22]	S. Kaczmarz, Angenäherte Auflösung von systemen linearer gleichungen, Bull. Int. Acad. Pol. Sci. Lett. A, 35 (1937), 355–357.
[23]	S. P. Kolodziej, M. Aznaveh, M. Bullock, J. David, T. A. Davis, M. Henderson et al., The SuiteSparse matrix collection website interface, J. Open Source Softw., 4 (2019), 1244–1248. https://doi.org/10.21105/joss.01244 doi: 10.21105/joss.01244
[24]	Y. Liu, C. Q. Gu, On greedy randomized block Kaczmarz method for consistent linear systems, Linear Algebra Appl., 616 (2021), 178–200. https://doi.org/10.1016/j.laa.2021.01.024 doi: 10.1016/j.laa.2021.01.024
[25]	C. Q. Miao, W. T. Wu, On greedy randomized average block Kaczmarz method for solving large linear systems, J. Comput. Appl. Math., 413 (2022), 114372. https://doi.org/10.1016/j.cam.2022.114372 doi: 10.1016/j.cam.2022.114372
[26]	I. Necoara, Faster randomized block Kaczmarz algorithms, SIAM J. Matrix Anal. A., 40 (2019), 1425–1452. https://doi.org/10.1137/19M1251643 doi: 10.1137/19M1251643
[27]	D. Needell, J. A. Tropp, Paved with good intentions: Analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441 (2014), 199–221. https://doi.org/10.1016/j.laa.2012.12.022 doi: 10.1016/j.laa.2012.12.022
[28]	Y. Q. Niu, B. Zheng, A greedy block Kaczmarz algorithm for solving large-scale linear systems, Appl. Math. Lett., 104 (2020), 106294. https://doi.org/10.1016/j.aml.2020.106294 doi: 10.1016/j.aml.2020.106294
[29]	T. Strohmer, R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), 262–278. https://doi.org/10.1007/s00041-008-9030-4 doi: 10.1007/s00041-008-9030-4
[30]	C. Tompkins, Projection methods in calculation of some linear problems, Bull. Amer. Math. Soc., 55 (1949), 520.
[31]	L. Wen, F. Yin, Y. M. Liao, G. X. Huang, A greedy average block Kaczmarz method for the large scaled consistent system of linear equations, AIMS Math., 7 (2022), 6792–6806. https://doi.org/10.3934/math.2022378 doi: 10.3934/math.2022378
[32]	G. Wu, Q. Chang, Semi-randomized block Kaczmarz methods with simple random sampling for large-scale linear systems, arXiv: 2212.08797, 2023. https://doi.org/10.48550/arXiv.2212.08797
[33]	A. Q. Xiao, J. F. Yin, N. Zheng, On fast greedy block Kaczmarz methods for solving large consistent linear systems, Comput. Appl. Math., 42 (2023), 119. https://doi.org/10.1007/s40314-023-02232-x doi: 10.1007/s40314-023-02232-x
[34]	F. Yin, B. Y. Zhang, G. X. Huang, A partially block randomized extended Kaczmarz method for solving large overdetermined inconsistent linear systems, AIMS Math., 8 (2023), 18512–18527. https://doi.org/10.3934/math.2023941 doi: 10.3934/math.2023941
[35]	K. Zhang, F. T. Li, X. L. Jiang, Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems, Comput. Appl. Math., 41 (2022), 332. https://doi.org/10.1007/s40314-022-02044-5 doi: 10.1007/s40314-022-02044-5
[36]	Y. Zhang, H. Li, Block sampling Kaczmarz-Motzkin methods for consistent linear systems, Calcolo, 58 (2021), 39. https://doi.org/10.1007/s10092-021-00429-2 doi: 10.1007/s10092-021-00429-2
[37]	Y. Zhang, H. Li, Randomized block subsampling Kaczmarz-Motzkin method, Linear Algebra Appl., 667 (2023), 133–150. https://doi.org/10.1016/j.laa.2023.03.003 doi: 10.1016/j.laa.2023.03.003

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)