Jun 10 – 11, 2022
Dipartimento di Matematica, Università di Pisa
Europe/Rome timezone

Provable convergence rate for asynchronous methods via randomized linear algebra

Jun 11, 2022, 9:45 AM
Aula Magna (Dipartimento di Matematica, Università di Pisa)

Aula Magna

Dipartimento di Matematica, Università di Pisa

L.go B. Pontecorvo, 5 56127 Pisa (PI) Italy


Daniel Szyld (Temple University)


Asynchronous methods refer to parallel iterative procedures where each process performs its task without waiting for other processes to be completed, i.e., with whatever information it has locally available and with no synchronizations with other processes. For the numerical solution of a general partial differential equation on a domain, Schwarz iterative methods use a decomposition of the domain into two or more (usually overlapping) subdomains. In essence one is introducing
new artificial boundary conditions Thus each process corresponds to a local solve with boundary conditions from the values in the neighboring subdomains.

Using this method as a solver, avoids the pitfall of synchronization required by the inner products in Krylov subspace methods. A scalable method results with either optimized Schwarz or when a coarse grid is added. Numerical results are presented on large three-dimensional problems illustrating the efficiency of asynchronous parallel implementations.

Most theorems show convergence of the asynchronous methods, but not a rate of convergence. In this talk, using the concepts of randomized linear algebra, we present provable convergence rate for the methods for a class of nonsymmetric linear systems. A key element in the new results is the choice of norm for which we can prove convergence of the residual in the expected value sense.

Presentation materials

There are no materials yet.