different from the one considered in [MES94] and [SME95]. We consider the case where the nonlinear flow equations are diagonally monotone nondecreasing and offdiagonally monotone nonincreasing. This case is more general than M-functions. We also concentrate on a different class of mappings. We study submappings and supermappings, whereas we have considered a-submappings and asupermappings in [MES94] and [SME95]. Finally, we propose point iterative methods for nonlinear network flow problems, whereas the methods studied in [MES94] and [SME95] are essentially block iterative methods.
Flexible communication between processors is the main feature of the new class of methods presented in this paper. Asynchronous iterations with flexible communication admit more message exchanges than totally asynchronous iterations studied in [ChM69], [Mie75a], [Bau78], and [BeT89]. In particular, the current value of the components of the iteration vector resulting from intermediate steps of updating can be communicated to other processors. We recall that communications occur only at the end of each updating phase in totally asynchronous schemes of computation. Thus, the new class of methods proposed here allows each processor to communicate partial updates which are issued from computations in progress. We will see in the sequel that the use of such partial updates can speed up the convergence. We give a convergence result which is all new. We note that previous results in the literature (see [ChM69], [Mie75a], [Bau78], and [BeT89]) cannot be used in this context since they consider a different model of algorithms. An implementation of an asynchronous iterative method with flexible communication is proposed. Termination detection is considered. Finally, computational results on a distributed memory multiprocessor are presented and analyzed.
Section 2 deals with the convex network flow problem. Asynchronous iterative algorithms with flexible communication are presented in Section 3. An implementation is given in Section 4. Experimental results are presented and analyzed in Section 5. Conclusions are drawn in Section 6. The proof of the convergence result is presented in Section 7 (Appendix).