Talks
Dynamic Non-Uniform Randomization in Asynchronous Linear Solvers
Copper Mountain Conference on Iterative Methods, Copper Mountain, CO (Virtual) (2022) (Slides)(Code for the slides)Abstract/Overview
One approach to improving the performance of stationary linear solvers is to utilize asynchronous communication between the processors. In order to establish bounds on convergence rate, randomized various of asynchronous linear solvers have been studied. This approach has been examined previously for the case where the random selection is done uniformly and non-uniformly, however the probability of selecting any given component remains fixed through the algorithm and does not dynamically change. The idea behind the solvers considered here is for each processor to select the next component to update randomly, using a distribution that more heavily weights selection of components that are somehow more important to the solution. The main contribution is to evaluate the viability of changing the component ranking dynamically, and investigate the effect of various distributions in selecting from this dynamic list.
This updating procedure is motivated by the Southwell iteration, which selects the component with the largest contribution to the residual at each iteration and which can converge in fewer iterations than traditional relaxation schemes; previous work has also shown that Southwell type iterations can converge faster than uniform random selection. There is a balance between the extra computational time required to intelligently select components, and the savings in total iterations. Updating all the residuals every iteration likely introduces too much computational overhead to be of practical use, and techniques are explored for lessening this computational burden.