Title: Redundant Computations in a Fixed Point Linear Solver for Collaborative Autonomy
Abstract: Unreliable computing environments impose several additional constraints on algorithmic approaches, including the presence of communication delays among network elements, heterogeneous computing architectures, and the need for fully decentralized algorithms. Our goal is to adapt the asynchronous parallel Jacobi method to fully utilize these environments by incorporating the idea of redundant computations. The redundant asynchronous parallel Jacobi algorithm partitions a linear system among computing elements, e.g., processors, while allowing overlap such that each component of the solution vector is updated by at least one other processor. Redundant computations are introduced primarily to address the issue of delayed communications. In order to improve the quality of the iterative scheme, we loosen the constraint that the performance of the algorithm relies on the performance of the slowest processor. We present a new framework for analyzing redundant asynchronous linear system solvers and present numerical results for the case where the Jacobi iteration matrix is nonnegative.