A greedy average block Kaczmarz method for the large scaled consistent system of linear equations

Li Wen; Feng Yin; Yimou Liao; Guangxin Huang; Li Wen; Feng Yin; Yimou Liao; Guangxin Huang

doi:10.3934/math.2022378

AIMS Mathematics

2022, Volume 7, Issue 4: 6792-6806. doi: 10.3934/math.2022378

Previous Article Next Article

Research article

A greedy average block Kaczmarz method for the large scaled consistent system of linear equations

1.
College of Mathematics and Statistics, Sichuan University of Science and Engineering, Zigong 643000, China
2.
Sichuan Province University Key Laboratory of Bridge Non-destruction Detecting and Engineering Computing, Sichuan University of Science and Engineering, Zigong 643000, China
3.
College of Mathematics and Physics, Geomathematics Key Laboratory of Sichuan, Chengdu University of Technology, Chengdu 610059, China

Received: 03 November 2021 Revised: 04 January 2022 Accepted: 10 January 2022 Published: 26 January 2022
MSC : 65F10, 65F45

This paper presents a greedy average block Kaczmarz (GABK) method to solve the large scaled consistent system of linear equations. The GABK method introduces the strategy of extrapolation process to improve the GBK algorithm and to avoid computing the Moore-Penrose inverse of a submatrix of the coefficient matrix determined by the block index set. The GABK method is proved to converge linearly to the least-norm solution of the consistent system of linear equations. Numerical examples show that the GABK method has the best efficiency and effectiveness among all methods compared.
- block Kaczmarz,
- extrapolated stepsize,
- greedy strategy,
- GABK
Citation: Li Wen, Feng Yin, Yimou Liao, Guangxin Huang. A greedy average block Kaczmarz method for the large scaled consistent system of linear equations[J]. AIMS Mathematics, 2022, 7(4): 6792-6806. doi: 10.3934/math.2022378

Related Papers:

Abstract

This paper presents a greedy average block Kaczmarz (GABK) method to solve the large scaled consistent system of linear equations. The GABK method introduces the strategy of extrapolation process to improve the GBK algorithm and to avoid computing the Moore-Penrose inverse of a submatrix of the coefficient matrix determined by the block index set. The GABK method is proved to converge linearly to the least-norm solution of the consistent system of linear equations. Numerical examples show that the GABK method has the best efficiency and effectiveness among all methods compared.

References

[1]	S. Kaczmarz, Angenäherte auflösung von systemen linearer gleichungen, International Bulletin of the Polish Academy of Sciences, Letters A, 35 (1937), 355–357.
[2]	R. Gordon, R. Bender, G. Herman, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, J. Theor. Biol., 29 (1970), 471–481. http://dx.doi.org/10.1016/0022-5193(70)90109-8 doi: 10.1016/0022-5193(70)90109-8
[3]	C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl., 20 (2004), 103. http://dx.doi.org/10.1088/0266-5611/20/1/006 doi: 10.1088/0266-5611/20/1/006
[4]	Y. Censor, Parallel application of block-iterative methods in medical imaging and radiation therapy, Math. Program., 42 (1988), 307–325. http://dx.doi.org/10.1007/BF01589408 doi: 10.1007/BF01589408
[5]	G. Herman, Image reconstruction from projections: the fundamentals of computerized tomography, New York: Academic Press, 1980.
[6]	J. Elble, N. Sahinidis, P. Vouzis, Gpu computing with Kaczmarz's and otheriterative algorithms for linear systems, Parallel Comput., 36 (2010), 215–231. http://dx.doi.org/10.1016/j.parco.2009.12.003 doi: 10.1016/j.parco.2009.12.003
[7]	T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numer. Math., 35 (1980), 1–12. http://dx.doi.org/10.1007/BF01396365 doi: 10.1007/BF01396365
[8]	P. Eggermont, G. Herman, A. Lent, Iterative algorithms for large partitioned linear systems, with applications to image reconstruction, Linear Algebra Appl., 40 (1981), 37–67. http://dx.doi.org/10.1016/0024-3795(81)90139-7 doi: 10.1016/0024-3795(81)90139-7
[9]	D. Needell, J. Tropp, Paved with good intentions: analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441 (2014), 199–221. http://dx.doi.org/10.1016/j.laa.2012.12.022 doi: 10.1016/j.laa.2012.12.022
[10]	D. Needell, R. Zhao, A. Zouzias, Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra Appl., 484 (2015), 322–343. http://dx.doi.org/10.1016/j.laa.2015.06.027 doi: 10.1016/j.laa.2015.06.027
[11]	J. Chen, Z. Huang, On the error estimate of the randomized double block Kaczmarz method, Appl. Math. Comput., 370 (2019), 124907. http://dx.doi.org/10.1016/j.amc.2019.124907 doi: 10.1016/j.amc.2019.124907
[12]	R. Gower, P. Richtárik, Rndomized iterative methods for linear systems, SIAM J. Matrix Anal. Appl., 36 (2015), 1660–1690. http://dx.doi.org/10.1137/15M1025487 doi: 10.1137/15M1025487
[13]	I. Necoara, Faster randomized block Kaczmarz algorithms, SIAM J. Matrix Anal. Appl., 40 (2019), 1425–1452. http://dx.doi.org/10.1137/19M1251643 doi: 10.1137/19M1251643
[14]	Y. Niu, B. Zheng, A greedy block Kaczmarz algorithm for solving large-scale linear systems, Appl. Math. Lett., 104 (2020), 106294. http://dx.doi.org/10.1016/j.aml.2020.106294 doi: 10.1016/j.aml.2020.106294
[15]	Z. Bai, W. Wu, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606. http://dx.doi.org/10.1137/17M1137747 doi: 10.1137/17M1137747
[16]	J. Chen, Z. Huang, On a fast deterministic block Kaczmarz method for solving large-scale linear systems, Numer. Algor., in press. http://dx.doi.org/10.1007/s11075-021-01143-4
[17]	K. Du, W. Si, X. Sun, Randomized extended average block Kaczmarz for solving least squares, SIAM J. Sci. Comput., 42 (2020), A3541–A3559. http://dx.doi.org/10.1137/20M1312629 doi: 10.1137/20M1312629
[18]	Y. Liu, C. Gu, On greedy randomized block Kaczmarz method for consistent linear systems, Linear Algebra Appl., 616 (2021), 178–200. http://dx.doi.org/10.1016/j.laa.2021.01.024 doi: 10.1016/j.laa.2021.01.024
[19]	T. Davis, Y. Hu, The university of Florida sparse matrix collection, ACM T. Math. Software, 38 (2011), 1–25. http://dx.doi.org/10.1145/2049662.2049663 doi: 10.1145/2049662.2049663

Reader Comments

Your name:*

Email:*
© 2022 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)