Skip to main content


Swipe to navigate through the articles of this issue

01-09-2021 | Issue 3/2021

Calcolo 3/2021

Block sampling Kaczmarz–Motzkin methods for consistent linear systems

Calcolo > Issue 3/2021
Yanjun Zhang, Hanyu Li
Important notes
This work was funded by the National Natural Science Foundation of China (No. 11671060) and the Natural Science Foundation Project of CQ CSTC (No. cstc2019jcyj-msxmX0267).

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


The sampling Kaczmarz–Motzkin (SKM) method is a generalization of the randomized Kaczmarz method and the Motzkin method. It first samples some rows of coefficient matrix randomly to build a set and then makes use of the maximum violation criterion within this set to determine a constraint. Finally, it makes progress by enforcing this single constraint. In this paper, based on the SKM method and the block strategies, we present two block sampling Kaczmarz–Motzkin methods for consistent linear systems. Specifically, we also first sample a subset of rows of coefficient matrix and then determine an index in this set using the maximum violation criterion. Unlike the SKM method, in the block methods, we devise different greedy strategies to build index sets. Then, the new methods make progress by enforcing the corresponding multiple constraints simultaneously. Numerical experiments show that, for the same accuracy, our methods outperform the SKM method and the famous deterministic method, i.e., the CGLS method, in terms of the number of iterations and computing time.

Please log in to get access to this content

About this article

Other articles of this Issue 3/2021

Calcolo 3/2021 Go to the issue

Premium Partner

    Image Credits