Title: Convergence of Randomized and Greedy Block Gauss-Seidel methods,

and Asynchronous Iterations

Affiliation: Temple University

Abstract: We extend results known for the randomized (point and block) 

Gauss-Seidel and the Gauss-Southwell methods for the case of a Hermitian and positive definite matrix to certain classes of non-Hermitian matrices. We consider cases with overlapping variables (as in Domain Decomposition). We obtain convergence results for a whole range of parameters describing the probabilities in the randomized method or the greedy choice strategy in the Gauss-Southwell-type methods. We identify those choices which make our convergence bounds best possible. One result is that the best convergence bounds that we obtain for the expected values in the randomized algorithm are as good as the best for the deterministic, but more costly algorithms of Gauss-Southwell type. We use these new results to show a provable convergence rate for asynchronous iterations.