A probabilistic analysis of asynchronous iteration (Q1611861)

\textit{D. Chazan} and \textit{W. Miranker} [ibid. 2, 199-222 (1969; Zbl 0225.65043)] introduced the chaotic scheme (now called asynchronous iteration) to implement iterative linear solvers in parallel settings and give conditions to ensure convergence of the schemes. In this paper weaker conditions for convergence are given using a probabilistic approach to describe the updates in the asynchronous scheme. For a shared memory computer the model is described using the probability \(p_\ell\) of a given component \(\ell\) (which may be a block) is updated in a given step and the probability \(s_q\) of the delay is \(q\) steps. Assuming the system is written as \((I-B)x=d\), arranging the probabilities \(p_\ell\) in a diagonal matrix \(P\), defining the generating function of the delay probabilities \(s(z)=\sum_{\nu=0}^{\infty} s_q z^q\), and the matrices \(M(z) = I -z (I-P+s(z)PB)\), some convergence results are established. For example it is proved that a necessary condition for the expected value of the solution to converge for all initial guesses is the non-singularity of \(M(z)\) for all \(z\) in \(|z|<1\). On the other side if \(M(z)\) is analytic and non-singular in \(|z|<R\), \(1<R\), then the expected value of the solution converges and the expected value in the \(\mu\)-th iteration is \(\|E^\mu(x)\|=O(R^{-\mu})\). Other sufficient conditions for convergence are stated without proof. In what follows the author considers the case that the matrix \(B\) satisfies the weighting assumption if there exists a diagonal matrix \(D\) with positive entries on the main diagonal, such that \(B^TDB < D\). If this condition is fullfilled then it is proved that \(M(z)\) is non-singular for \(|z|\leq 1\) and any diagonal probability matrix \(P\). Later it is proved that the weighting condition, and the finiteness of the expected value of the delay, \(s'(1)\), and the initial variance are sufficient conditions for the convergence of the variance. There is also stated that when \(s'(1)\) is finite then the sum of variances is finite for all initial data. The model for distributed memory is analyzed and sufficient conditions for the convergence of the variance ones are given. For the over and under relaxed schemes similar results to the previous ones are given. Numerical simulations using Matlab are performed on \(5 \times 5\) and \(10 \times 10\) matrices to illustrate the theoretical results. Finally it is proved that the condition \(\rho(|B|)<1\) given by Chazan and Miranker [loc. cit.] implies the weighting condition, so the conditions given in this paper are weaker than the conditions given by Chazan and Miranker [loc. cit.]. It is also proved that the weighting condition implies that \(\rho_{\pm}(B):=\max_{\vec{\theta}} \rho(S(\vec{\theta})B)<1\), where \(S(\vec{\theta}) := \text{diag}(e^{i\theta_k})\), and \(\vec{\theta}\in \mathbb{R}^n\), however it is not clear if the reciprocal is true or not.