Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons

Open Access. Powered by Scholars. Published by Universities.®

Numerical Analysis and Computation

Scripps Senior Theses

Theses/Dissertations

2017

Articles 1 - 1 of 1

Full-Text Articles in Physical Sciences and Mathematics

Paving The Randomized Gauss-Seidel, Wei Wu Jan 2017

Paving The Randomized Gauss-Seidel, Wei Wu

Scripps Senior Theses

The Randomized Gauss-Seidel Method (RGS) is an iterative algorithm that solves overdetermined systems of linear equations Ax = b. This paper studies an update on the RGS method, the Randomized Block Gauss-Seidel Method. At each step, the algorithm greedily minimizes the objective function L(x) = kAx bk2 with respect to a subset of coordinates. This paper describes a Randomized Block Gauss-Seidel Method (RBGS) which uses a randomized control method to choose a subset at each step. This algorithm is the first block RGS method with an expected linear convergence rate which can be described by the properties of the matrix …