Enhancing Asynchronous Linear Solvers Through Randomization

Asynchronous iterative methods present a mechanism to improve the performance of parallel algorithms for highly parallel computational platforms by removing the overhead associated with synchronization among computing elements. This paper considers a class of asynchronous iterative linear system solvers that employ randomization to determine the component update orders, and specifically focusing on the effects of non-uniform distributions. Results show that using distributions favoring the selection of components with a larger residual may lead to a faster convergence than that when selecting uniformly. In particular, in the best case of parameter choices, average times for the normal and exponential distributions were, respectively, 13.3% and 17.3% better than the performance with a uniform distribution.