Cooperative concurrent asynchronous computation of the solution of symmetric linear systems

Abstract

This paper extends the idea of Brezinski's hybrid acceleration procedure, for the solution of a system of linear equations with a symmetric coefficient matrix of dimension n, to a new context called cooperative computation, involving m agents (m << n), each one concurrently computing the solution of the whole system, using an iterative method. Cooperation occurs between the agents through the communication, periodic or probabilistic, of the estimate of each agent to one randomly chosen agent, thus characterizing the computation as concurrent and asynchronous. Every time one agent receives solution estimates from the others, it carries out a least squares computation, involving a small linear system of dimension m, in order to replace its current solution estimate by an affine combination of the received estimates, and the algorithm continues until a stopping criterion is met. In addition, an autocooperative algorithm, in which estimates are updated using affine combinations of current and past estimates, is also proposed. The proposed algorithms are shown to be efficient for certain matrices, specifically in relation to the popular Barzilai-Borwein algorithm, through numerical experiments.