APRK: an accelerated parallel randomized iterative algorithm for solving large-scale sparse overdetermined linear systems

In this paper, we propose a new preconditioning strategy that combines the MPI parallel computing framework of the Shanhe Supercomputing Platform with the Kaczmarz method based on maximum distance sampling. The traditional Kaczmarz method, which iteratively solves overdetermined linear systems by randomly sampling matrix rows, often suffers from slow convergence. Our approach incorporates weighted averaging to reduce data redundancy and enhance data representation. By leveraging the MPI parallel computing framework, we integrate greedy sampling with CountSketch preprocessing, optimizing data compression and dimensionality reduction processes. Numerical experiments demonstrate that our method significantly accelerates convergence and improves computational efficiency compared to traditional and non-preconditioned Kaczmarz methods, making it particularly suitable for solving large-scale overdetermined linear systems in parallel computing environments.