Speaker
Description
Asynchronous iterative methods, such as Asynchronous Jacobi, offer a promising mechanism for overcoming synchronization bottlenecks in massively parallel and heterogeneous computing environments. By allowing processing elements to update components using the latest available data without global barriers, these methods maximize computational throughput. However, asynchrony also makes performance more sensitive to the order in which unknowns (or blocks of unknowns) are updated, since processors may act on delayed information and progress unevenly. While randomized numerical linear algebra has provided bounds for asynchronous solvers using uniform sampling, this approach ignores the local error distribution, potentially wasting updates on converged components.
We consider a family of sampling strategies that range from uniform randomization to non-uniform importance sampling, and then to dynamic, time-varying distributions that adapt online using inexpensive residual-based indicators. The main theoretical focus is on convergence in expectation under randomized update rules. To make the analysis transparent, we begin with a synchronous randomized model and establish conditions under which the associated sampling schemes yield expected decrease in a suitable error measure. We then carry the same randomization patterns to an asynchronous setting, showing how mild assumptions on delays and update coverage allow the expected contraction arguments to be extended, while making explicit where asynchrony changes the requirements and the bounds.