Rahul Jain

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2022-52
May 10, 2022

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-52.pdf

In the past, algorithms for solving linear systems of equations have focused on finding a solution that is not only stable with respect to small changes to the input, but with a very small error with respect to the analytical solution. However, this comes at the cost of an increased runtime. There has been an increased need to find a solution to linear system in a small amount of time, requiring modest accuracy. Randomized algorithms are quite beneficial in this aspect in that they can have a smaller runtime than their deterministic counterparts. In this thesis, we explore and then modify Randomized Block Kaczmarz, a randomized algorithm for solving overdetermined linear systems of equations, to see how practically effective it can be.

Advisor: James Demmel

BibTeX citation:

@mastersthesis{Jain:EECS-2022-52,
    Author = {Jain, Rahul},
    Title = {Tuning Doubly Randomized Block Kaczmarz Method},
    School = {EECS Department, University of California, Berkeley},
    Year = {2022},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-52.html},
    Number = {UCB/EECS-2022-52},
    Abstract = {In the past, algorithms for solving linear systems of equations have focused on finding a solution that is not only stable with respect to small changes to the input, but with a very small error with respect to the analytical solution. However, this comes at the cost of an increased runtime. There has been an increased need to find a solution to linear system in a small amount of time, requiring modest accuracy. Randomized algorithms are quite beneficial in this aspect in that they can have a smaller runtime than their deterministic counterparts. In this thesis, we explore and then modify Randomized Block Kaczmarz, a randomized algorithm for solving overdetermined linear systems of equations, to see how practically effective it can be.}
}

EndNote citation:

%0 Thesis
%A Jain, Rahul
%T Tuning Doubly Randomized Block Kaczmarz Method
%I EECS Department, University of California, Berkeley
%D 2022
%8 May 10
%@ UCB/EECS-2022-52
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-52.html
%F Jain:EECS-2022-52