Convergence of Randomized and Greedy Block Gauss-Seidel methods, as well as Asynchronous Iterations

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.(Joint work with Andreas Frommer)

Daniel B. Szyld - Bio

Daniel B. Szyld

Daniel B. Szyld is Professor of Mathematics at Temple University.

Until recently he was the President of the International Linear Algebra Society (2020-2026).

He was Vice-President (at large) of SIAM, the Society for Industrial and Applied Mathematics in 2014-2015.

He was the editor-in-chief of the SIAM Journal on Matrix Analysis and Applications (2015-2020) and of the Electronic Transactions on Numerical Analysis (2005-2013).

He is a SIAM Fellow, and an AMS Fellow. He has worked on many aspects of numerical linear algebra and matrix computations, including eigenvalue problems, sparse matrix techniques, Schwarz preconditioning and domain decomposition, Krylov subspace methods, and asynchronous iterative methods. His PhD is from the Courant Institute, New York University (1983),which he attended after undergraduate studies in his native Buenos Aires.