A doubly stochastic block Gauss–Seidel algorithm for solving linear equations

作者：

Highlights：

• A simple doubly stochastic block Gauss-Seidel algorithm for solving linear systems of equations is proposed.

• The new algorithm is projection-free and at each step a randomly picked submatrix is used to update the iterate.

• The convergence theory of the new algorithm is established.

• The new algorithm can be much more efficient than some of the existing algorithms.

摘要

•A simple doubly stochastic block Gauss-Seidel algorithm for solving linear systems of equations is proposed.•The new algorithm is projection-free and at each step a randomly picked submatrix is used to update the iterate.•The convergence theory of the new algorithm is established.•The new algorithm can be much more efficient than some of the existing algorithms.

论文关键词：Randomized Kaczmarz,Randomized coordinate descent,Doubly stochastic Gauss–Seidel,Doubly stochastic block Gauss–Seidel,Exponential convergence

论文评审过程：Received 8 June 2020, Revised 18 March 2021, Accepted 15 May 2021, Available online 31 May 2021, Version of Record 31 May 2021.

论文官网地址：https://doi.org/10.1016/j.amc.2021.126373