Mathematics of Computation

Author(s): J. C. Miellou; D. El Baz; P. Spiteri.
Journal: Math. Comp. 67 (1998), 237-255.
MSC (1991): Primary 65N12, 65N55, 68Q10, 68Q22
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract: This paper deals with a new class of parallel asynchronous iterative algorithms for the solution of nonlinear systems of equations. The main feature of the new class of methods presented here is the possibility of flexible communication between processors. In particular partial updates can be exchanged. Approximation of the associated fixed point mapping is also considered. A detailed convergence study is presented. A connection with the Schwarz alternating method is made for the solution of nonlinear boundary value problems. Computational results on a shared memory multiprocessor IBM 3090 are briefly presented.

1.: M. Bahi, and J.-C. Miellou, Contractive mappings with maximum norms: comparisons of constants of contraction and application to asynchronous iterations, Parallel Computing 19 (1993), 511-523. MR 94c:65072
2.: R. H. Barlow and D. J. Evans, Synchronous and asynchronous iterative parallel algorithms for linear systems, Comput. J. 25 (1982), 56-60.
3.: G. M. Baudet, Asynchronous iterative methods for multiprocessors, J. Assoc. Comput. Mach. 25 (1978), 226-244. MR 58:13674
4.: D. P. Bertsekas, Distributed dynamic programming, IEEE Trans. Auto. Contr. 27 (1982), 610-616. MR 83k:90124
5.: D. P. Bertsekas, Distributed asynchronous computation of fixed points, Mathematics Programming 27 (1983), 107-120. MR 85a:68051
6.: D. P. Bertsekas and D. El Baz, Distributed asynchronous relaxation methods for convex network flow problems, SIAM J. Control Optim. 25 (1987), 74-85. MR 88f:90061
7.: D. P. Bertsekas and J. Tsitsiklis, Parallel and distributed computation, Numerical Methods, Englewood Cliffs, Prentice Hall, 1989.
8.: D. Chazan and W. Miranker, Chaotic relaxation, Linear Algebra and Appl. 2 (1969), 199-222. MR 40:5114
9.: P. Cousot, Méthodes itératives de construction et d'approximation de points fixes d'opérateurs monotones sur un treillis, analyse sémantique des programmes, Thèse d'Etat, Université de Grenoble (1978).
10.: D. El Baz, $M$ -functions and parallel asynchronous algorithms, SIAM J. Numer. Anal. 27 (1990), 136-140. MR 91e:65165
11.: D. El Baz, Asynchronous gradient algorithms for a class of convex separable network flow problems, Computational Optimization and Applications 5 (1996), 187-205. CMP 96:12
12.: D. El Baz, Asynchronous implementation of relaxation and gradient algorithms for convex network flow problems, Parallel Computing 19 (1993), 1019-1028.
13.: D. El Baz, Nonlinear systems of equations and parallel asynchronous iterative algorithms, Advances in Parallel Computing 9, North-Holland, Amsterdam, 1994, 89-96.
14.: D. El Baz, P. Spiteri, and J.-C. Miellou, Distributed asynchronous iterative methods with order intervals for a class of nonlinear optimization problems, Journal of Parallel and Distributed Computing 38 (1996), 1-15.
15.: M. N. El Tarazi, Some convergence results for asynchronous algorithms, Numerical Math. 39 (1982), 325-340. MR 84a:65041
16.: M. N. El Tarazi, Algorithmes mixtes asynchrones, Etude de la convergence monotone, Numer. Math. 44 (1984), 363-369. MR 86c:65042
17.: D. J. Evans and W. Deren, An asynchronous parallel algorithm for solving a class of nonlinear simultaneous equations, Parallel Computing 17 (1991), 165-180. MR 92f:65166
18.: A. Frommer, On asynchronous iterations in partially ordered spaces, Numer. Funct. Anal. and Optimiz. 12 (1991), 315-325. MR 92m:54060
19.: A. Frommer and H. Schwandt, Asynchronous parallel methods for enclosing solutions of nonlinear equations, J. Comput. Appl. Math. 60 (1995), 47-62. MR 96f:65062
20.: L. Giraud and P. Spiteri, Résolution parallèle de problèmes aux limites non linéaires, RAIRO Modél. Math. Anal. Numér. 25 (1991), 73-100. MR 92d:65244
21.: L. Giraud and P. Spiteri, Implementations of parallel solutions for nonlinear boundary value problems, Parallel Computing '91, Advances in Parallel Computing (Evans, Joubert, Liddel, Editors), North-Holland, Amsterdam, 1992, 203-211. CMP 93:04
22.: R. W. Hockney and C. R. Jesshope, Parallel Computers 2, Adam Hilger, Bristol, 1988.
23.: P. L. Lions and B. Mercier, Approximation numérique des équations de Hamilton-Jacobi-Bellman, RAIRO Analyse numérique 14 (1980), 369-393. MR 82b:65055
24.: J.-C. Miellou, Itérations chaotiques à retards, C.R. Acad. Sci. Paris 278 (1974), 957-960. MR 50:15325
25.: J.-C. Miellou, Itérations chaotiques à retards, étude de la convergence dans le cas d'espaces partiellement ordonnés, C. R. Acad. Sci. Paris 280 (1975), 233-236. MR 52:12320
26.: J.-C. Miellou, Algorithmes de relaxation chaotique à retards, RAIRO R1, (1975), 55-82. MR 55:13772
27.: J.-C. Miellou, Asynchronous iterations and order intervals, Parallel Algorithms (M. Cosnard et al., eds.) North-Holland, Amsterdam, 1986, 85-96. MR 88f:65083
28.: J.-C. Miellou, Ph. Cortey-Dumont, and M. Boulbrachêne, Perturbation of fixed-point iterative methods, Advances in Parallel Computing 1, JAI Press Inc., 1990, 81-122.
29.: J.-C. Miellou and P. Spiteri, Un critère de convergence pour des méthodes générales de point fixe, RAIRO Modél. Math. Anal. Numér. (1985), 170-201. MR 87f:47098
30.: J. M. Ortega, Introduction to Parallel and Vector Solution of Linear Systems, Plenum Press, New York, 1988. MR 92i:65220a
31.: J. M. Ortega and W. C. Rheinboldt, Iterative Solutions of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. MR 42:8686
32.: W. C. Rheinboldt, On $M$ -functions and their application to nonlinear Gauss-Seidel iterations and to network flows, J. Math. Anal. and Appl. 32 (1970), 274-307. MR 42:3997
33.: F. Robert, M. Charnay, and F. Musy, Itérations chaotiques série parallèle pour des équations non linéaires de point fixe, Aplikace Math. 20 (1975), 1-38. MR 51:9472
34.: U. Schendel, Introduction to Numerical Methods for Parallel Computers, Ellis Horword, Chichester, 1984. MR 87j:65003
35.: P. Spiteri, Simulation d'exécutions parallèles pour la résolution d'inéquations varitionnelles stationnaires, 1er Coll. Int. GAMNI Méthodes Vectorielles et Parallèles en Calcul Scientifique, Paris, Rev. EDF Ser. C (1) (1983), 149-159. MR 85b:65122
36.: P. Spiteri, Parallel asynchronous algorithms for solving boundary value problems, in Parallel Algorithms (M. Cosnard et al., eds.), North-Holland, Amsterdam, 1986, 73-84. MR 88a:65158
37.: P. Spiteri, J.-C. Miellou and D. El Baz, Asynchronous alternating Schwarz method for the solution of nonlinear partial differential equations, IRIT report 95-17-R, LCS 195.10, LAAS Report 95309 (1995).
38.: R. Varga, Matrix iterative analysis, Prentice Hall, Englewood Cliffs, 1962. MR 28:1725

Retrieve articles in Mathematics of Computation with MSC (1991): 65N12, 65N55, 68Q10, 68Q22

J. C. Miellou
Affiliation: L.C.S. URA CNRS n$^\circ$ 040741, Université de Franche-Comté, 16, Route de Gray, 25030 Besançon Cedex, France
Email: miellou@comte.univ-fcomte.fr

D. El Baz
Affiliation: LAAS du CNRS L.P. CNRS 8001, 7, Avenue du Colonel Roche, 31077 Toulouse Cedex, France

P. Spiteri
Affiliation: ENSEEIHT-IRIT UA CNRS 1399, LIMA, Institut National Polytechnique de Tou- louse, 2, Rue Camichel, 31071 Toulouse Cedex, France

DOI: 10.1090/S0025-5718-98-00885-0
PII: S 0025-5718(98)00885-0
Keywords: Parallel iterative methods, asynchronous iterations, Schwarz alternating method, domain decomposition methods, boundary value problems
Received by editor(s): December 9, 1994
Received by editor(s) in revised form: January 26, 1996 and July 19, 1996
Copyright of article: Copyright 1998, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS