The Greedy Partially Randomized Extended Gauss-Seidel Method For Solving The Large Linear Systems

In many practical problems,we often need to solve a ultra-large-scale systems of linear equations.When we use the classical Krylov subspace methods or the matrix splitting iteration methods to solve this kind of linear systems,the amount of storage required increases very fast as the scale of the linear system becomes large.To overcome this difficulty,many researchers in recent years have focused themselves on the randomized iterative methods since the storage required by the randomized iterative methods is far fewer than these existing classical iterative methods.In this work,based on the greedy Kaczmarz algorithm,we propose a greedy coordinate descent(GCD)method,and prove that the iteration sequence generated by the GCD method converges to the Moore-Penrose pseudoinverse solution A(?)b of the system of linear equations Ax=b when the matrix A is of full column rank.Numerical results show that the GCD method is more efficient than the randomized coordinate descent(RCD)method.Furthermore,note that the randomized extended Gauss-Seidel(REGS)algorithm can be used for solving many types of linear systems(consistent or inconsistent,full rank or rank deficient),we construct a greedy partially REGS(GPREGS)method by replacing its inner RCD method with the more efficient GCD method.Theoretical analysis demonstrates that the GPREGS method converges in expectation to the Moore-Penrose pseudoinverse solution and numerical results show that the GPREGS method is more efficient than the REGS method.