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

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.