A probabilistic analysis of asynchronous iteration
\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.
- A convergence theorem for chaotic asynchronous relaxation
- Asynchronous Iterative Methods for Multiprocessors
- Chaotic relaxation
- scientific article; zbMATH DE number 3720254 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- On asynchronous iterations
- Convergence analysis of asynchronous linear iterations with stochastic delays
- On asynchronous iterations
- On Monte Carlo methods in distributed memory systems
- Asynchronous iterations with flexible communication: contracting operators
- Further results on convergence of asynchronous linear iterations
- Performance analysis of asynchronous parallel Jacobi
- On the convergence of asynchronous parallel iteration with unbounded delays
- On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations
- scientific article; zbMATH DE number 1788242 (Why is no real title available?)
- Random Relaxation of Fixed-Point Iteration
- Consensus-based distributed sensor calibration and least-square parameter identification in WSNs
- On the convergence of parallel asynchronous block-iterative computations
This page was built for publication: A probabilistic analysis of asynchronous iteration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1611861)
