MATH Seminar

Title: Asynchronous Iterative Methods for Solving Sparse Linear Systems
Seminar: Computational Mathematics
Speaker: Jordi Wolfson-Pou of Georgia Institute of Technology
Contact: Yuanzhe Xi,
Date: 2019-10-18 at 2:00PM
Venue: MSC W303
Download Flyer
Reducing synchronization in iterative methods for solving large sparse linear systems may become one of the most important goals for such solvers on exascale computers. Research in asynchronous iterative methods has primarily considered the asymptotic behavior of basic iterative methods, e.g., Jacobi. However, practical behavior of basic iterative methods has not been extensively studied, and little research has been done on asynchronous multigrid methods. In this talk, the transient behavior of asynchronous Jacobi is examined. A simplified model of asynchronous Jacobi is analyzed, and results from shared and distributed memory experiments are presented to support the analysis. Two important results are shown. First, if a process is slower than all others (delayed in its computation), asynchronous Jacobi can continue to reduce the residual, even if the number of delayed iterations is similar in value to the size of the matrix. This result demonstrates how useful asynchronous Jacobi can be on heterogeneous architectures or for problems with large load imbalances, where some processes can be significantly slower than others. Second, asynchronous Jacobi can converge when synchronous Jacobi does not, and the convergence rate of asynchronous Jacobi can increase with increased concurrency. This is an important result when considering the amount of concurrency in future exascale machines; removing synchronization points not only reduces overall wall-clock time on its own, but also can allow convergence in fewer iterations, which further reduces the overall execution time. Asynchronous multigrid methods are also examined in this talk. Models of asynchronous additive multigrid methods are introduced, and a parallel implementation of asynchronous multigrid is presented. Experimental results show that asynchronous multigrid can exhibit grid-size independent convergence and can be faster than classical multigrid in terms of solve wall-clock time.

See All Seminars