Research On The Randomized Kaczmarz Algorithm And Its Variants

A large number of problems in scientific computing are related to how to efficiently solve large linear systems,such as fluid mechanics,structural mechanics,data processing,numerical weather prediction,computerized tomography,signal processing,power system optimization design,image reconstruction,high-dimensional differential equation,etc.In fact,many of the coefficient matrices of linear systems involved in the simulation of engineering problems above have certain specific structures.The scientific use of these structural characteristics to construct fast and robust linear system solvers is a current research focus.In this paper,a systematic research on the efficient solution of two types of linear systems(consistent or inconsistent)is carried out.Firstly,a two-subspace greedy randomized Kaczmarz method with a control param-eter ? for solving consistent linear systems(abbreviated as 2S-GRK(?)method)is pro-posed.This method is based on the two-subspace randomized Kaczmarz method(ab-breviated as 2S-RK method)for solving consistent coherent linear systems proposed by Needell and Ward.In the 2S-RK method,at each iteration,select two distinct working rows uniformly at random.However,the criterion of selecting rows is not optimal.It is a natural idea for us to take into consideration certain more efficient selection strategies of working rows rather than uniform random selection for the 2S-RK method in order to fur-ther improve its convergence properties,as enlightened by the superiority of the Kaczmarz method with nonuniform random selection over that with uniform random selection.In this paper,we establish a unified way to select working row indices for the 2S-RK method by introducing a control parameter ?,and derive a class of greedy generalization of the 2S-RK method named as the two-subspace greedy randomized Kaczmarz(2S-GRK(?))method.Moreover,the convergence properties of our proposed 2S-GRK(?)method is shown theoretically,and its feasibility and efficacy of our method are demonstrated in the numerical experiments.Secondly,a two-stage randomized extended Kaczmarz method(abbreviated as T-REK method)and a two-stage partially randomized extended Kaczmarz method(abbrevi-ated as T-PREK method)for solving inconsistent linear systems are proposed.These new methods are based on the randomized extended Kaczmarz method(referred to as REK method)proposed by Zouzias and Freris for solving the least squares problem.One step of the REK method consists of two components.The first component uses the randomized Kaczmarz method to obtained an approximate solution of the linear system;and the sec-ond component applies the randomized orthogonal projection method to obtain a vector approximating to 'noise'.Here we introduce a loop of obtaining a vector approximating to 'noise' into the REK method,and construct a two-stage randomized extended Kacz-marz(T-REK)method.Moreover,we propose a two-stage partially randomized extended Kaczmarz(T-PREK)method based on the T-REK method.In addition,the convergence analysis of our methods is given.Finally,the calculation results of the numerical example show that new methods are more efficient.