×

A chaotic asynchronous algorithm for computing the fixed point of a nonnegative matrix of unit spectral radius. (English) Zbl 0641.65033

One of the major problems in parallel computations is the communication between processors and their synchronization. The algorithm for the computation of a positive eigenvector to the unit eigenvalue of a positive, irreducible matrix of unit spectral radius described in this paper makes only mild assumptions with regard to the synchronization of the processors. The number and speed of the processors may vary within certain bounds. Geometric rate of convergence in a projective metric is demonstrated. Examples and counter examples which violate some of the assumptions and are not convergent are included, as well as numerical experiments which show the possible speed-up factor.
Reviewer: H. Matthies

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65Y05 Parallel numerical computation
15B51 Stochastic matrices
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
PDFBibTeX XMLCite
Full Text: DOI