RKOP:A Parallel Randomized Kaczmarz Algorithom Based on Oblique Projection for Large-Scale Overdetermined Equations

Résumé fourni par la source

The randomized Kaczmarz algorithm is a simple iterative method for solving overdetermined linear systems. However, the classical randomized Kaczmarz algorithm relies on orthogonal projections, and its convergence rate deteriorates significantly when the system exhibits a high linear dependence. This paper describes a novel oblique projection solution, RKOP, a randomized Kaczmarz algorithm with oblique projections based on maximum cosine similarity. Firstly, we select hyperplanes based on maximum cosine similarity and construct oblique projection directions using two hyperplanes to accelerate convergence. Secondly, a dynamic Monte Carlo error estimation method is employed to reduce the computational overhead of error evaluation effectively. Finally, we implement a multi-level parallel framework that achieves effective load balancing through optimized data distribution and uses a delayed update strategy to reduce computational overhead and improve overall efficiency significantly. Experimental results demonstrate that the serial version of RKOP achieves a$64.25 \times$speedup over the traditional randomized Kaczmarz algorithm. When scaled to 32 cores, RKOP achieves a$57.91 \times$speedup compared to its single-core version.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.