Monotonic sequences and rates of convergence of asynchronized iterative methods

Elsner L, Neumann M. Monotonic sequences and rates of convergence of asynchronized iterative methods. Linear algebra and its applications. 1993;180:17-33.In a recent paper B. Vemmer and the authors investigated the effect of varying the number of processors on the rate of convergence of the asynchronized parallel block Jacobi method associated with monotone matrices. It was found that, under certain simplifying assumptions, increasing the number of processors in relation to the number of blocks (or, what comes to the same in more general settings, the number of iteration operators) slows down the convergence. One interpretation for these results given in that paper was that increasing the number of processors means that when the current global approximation is updated by a local approximation from one of the processors, that local approximation was computed from a ''much'' earlier global approximation received from the host node. Hence the slowdown in the rate of convergence, The principal purpose of this paper is to remove some of the simplifying assumptions that were made in the above-mentioned paper and to prove that many of the results there hold under much more general conditions. Our present assumptions do not yield a fixed iteration matrix which models the process as was the case previously. This means that different tools have to be developed to establish results comparing the rate of convergence of two asynchronized processes