Greedy Motzkin–Kaczmarz methods for solving linear systems

Abstract The famous greedy randomized Kaczmarz (GRK) method uses the greedy selection rule on maximum distance to determine a subset of the indices of working rows. In this paper, with the greedy selection rule on maximum residual, we propose the greedy randomized Motzkin–Kaczmarz (GRMK) method for linear systems. The block version of the new method is also presented. We analyze the convergence of the two methods and provide the corresponding convergence factors. The computational complexities of the proposed methods are also given. Extensive numerical experiments show that the GRMK method has almost the same performance as the GRK method for dense matrices and the former performs better in computing time for some sparse matrices and some realistic practical problems, and their block versions have almost the same performance for most of cases.