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.

Advisors: 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