Graduation Year
2017
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Arts
Department
Mathematics
Reader 1
Deanna Needell
Reader 2
Winston Ou
Terms of Use & License Information
Rights Information
© 2017 Wei Wu
Abstract
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 A and its column submatrices. The analysis demonstrates that RBGS improves RGS more when given appropriate column-paving of the matrix, a partition of the columns into well-conditioned blocks. The main result yields a RBGS method that is more e cient than the simple RGS method.
Recommended Citation
Wu, Wei, "Paving the Randomized Gauss-Seidel" (2017). Scripps Senior Theses. 1074.
https://scholarship.claremont.edu/scripps_theses/1074
