A new class of asynchronous iterative algorithms with order intervals. (English) Zbl 0899.65031

Miellou, J. C.; El Baz, D.; Spiteri, P.

Math. Comput. 67, No. 221, 237-255 (1998).

The paper is devoted to the study of partial ordering techniques in order to obtain new parallel asynchronous iterative methods. For a given system of equations \(a(y) = 0\), a subproblem decomposition and associated fixed point mapping are considered for the solution via parallel asynchronous iterative methods with order intervals. The paper ends with the application of the obtained results to the Schwarz alternating method for the numerical solution of boundary value problems.

Reviewer: V.Berinde (Baia Mare)

MSC:

65H10	Numerical computation of solutions to systems of equations
65Y05	Parallel numerical computation
65N55	Multigrid methods; domain decomposition for boundary value problems involving PDEs

Keywords:

parallel asynchronous iterative methods; subdomain methods; Schwarz alternating method; boundary value problem; domain decomposition; order intervals

References:

[1]	M. Bahi and J.-C. Miellou, Contractive mappings with maximum norms: comparison of constants of contraction and application to asynchronous iterations, Parallel Comput. 19 (1993), no. 5, 511 – 523. · Zbl 0776.65040
[2]	R. H. Barlow and D. J. Evans, Synchronous and asynchronous iterative parallel algorithms for linear systems, Comput. J. 25 (1982), 56-60. · Zbl 0474.68044
[3]	Gérard M. Baudet, Asynchronous iterative methods for multiprocessors, J. Assoc. Comput. Mach. 25 (1978), no. 2, 226 – 244. · Zbl 0372.68015
[4]	Dimitri P. Bertsekas, Distributed dynamic programming, IEEE Trans. Automat. Control 27 (1982), no. 3, 610 – 616. · Zbl 0493.49030
[5]	Dimitri P. Bertsekas, Distributed asynchronous computation of fixed points, Math. Programming 27 (1983), no. 1, 107 – 120. · Zbl 0521.90089
[6]	Dimitri P. Bertsekas and Didier El Baz, Distributed asynchronous relaxation methods for convex network flow problems, SIAM J. Control Optim. 25 (1987), no. 1, 74 – 85. · Zbl 0624.90028
[7]	D. P. Bertsekas and J. Tsitsiklis, Parallel and distributed computation, Numerical Methods, Englewood Cliffs, Prentice Hall, 1989. · Zbl 0743.65107
[8]	D. Chazan and W. Miranker, Chaotic relaxation, Linear Algebra and Appl. 2 (1969), 199 – 222. · Zbl 0225.65043
[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]	Didier El Baz, \?-functions and parallel asynchronous algorithms, SIAM J. Numer. Anal. 27 (1990), no. 1, 136 – 140. · Zbl 0701.65040
[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. · Zbl 0780.90035
[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]	Mouhamed Nabih El Tarazi, Some convergence results for asynchronous algorithms, Numer. Math. 39 (1982), no. 3, 325 – 340 (French, with English summary). · Zbl 0479.65030
[16]	Mouhamed Nabih El Tarazi, Algorithmes mixtes asynchrones. Étude de convergence monotone, Numer. Math. 44 (1984), no. 3, 363 – 369 (French, with English summary). · Zbl 0568.65030
[17]	D. J. Evans and Wang Deren, An asynchronous parallel algorithm for solving a class of nonlinear simultaneous equations, Parallel Comput. 17 (1991), no. 2-3, 165 – 180. · Zbl 0729.65034
[18]	Andreas Frommer, On asynchronous iterations in partially ordered spaces, Numer. Funct. Anal. Optim. 12 (1991), no. 3-4, 315 – 325. · Zbl 0724.65063
[19]	Andreas Frommer and Hartmut Schwandt, Asynchronous parallel methods for enclosing solutions of nonlinear equations, J. Comput. Appl. Math. 60 (1995), no. 1-2, 47 – 62. Linear/nonlinear iterative methods and verification of solution (Matsuyama, 1993). · Zbl 0837.65051
[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), no. 5, 579 – 606 (French, with English summary). · Zbl 0733.65060
[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 · Zbl 0799.65129
[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 Anal. Numér. 14 (1980), no. 4, 369 – 393 (French, with English summary). · Zbl 0469.65041
[24]	Jean-Claude Miellou, Itérations chaotiques à retards, C. R. Acad. Sci. Paris Sér. A 278 (1974), 957 – 960 (French). · Zbl 0314.65028
[25]	Jean-Claude Miellou, Itérations chaotiques à retards; études de la convergence dans le cas d’espaces partiellement ordonnés, C. R. Acad. Sci. Paris Sér. A-B 280 (1975), A233 – A236 (French, with English summary). · Zbl 0332.65060
[26]	J. C. Miellou, Algorithmes de rélaxation chaotique à retards, Rev. Française Automat. Informat. Recherche Operationnelle Sér. \jname RAIRO Analyse Numérique 9 (1975), no. R-1, 55 – 82. · Zbl 0329.65038
[27]	Jean-Claude Miellou, Asynchronous iterations and order intervals, Parallel algorithms & architectures (Luminy, 1986) North-Holland, Amsterdam, 1986, pp. 85 – 96. · Zbl 0613.65071
[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]	Jean-Claude Miellou and Pierre Spiteri, Un critère de convergence pour des méthodes générales de point fixe, RAIRO Modél. Math. Anal. Numér. 19 (1985), no. 4, 645 – 669 (French, with English summary). · Zbl 0606.65042
[30]	Введение в параллел\(^{\приме}\)ные и векторные методы решения линейных систем, ”Мир”, Мосцощ, 1991 (Руссиан). Транслатед фром тхе Енглиш анд щитх а префаце бы Х. Д. Икрамов анд И. Е. Капорин; Щитх ан аппендиш бы Капорин; Транслатион едитед бы Икрамов.
[31]	J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. · Zbl 0241.65046
[32]	Werner C. Rheinboldt, On \?-functions and their application to nonlinear Gauss-Seidel iterations and to network flows, J. Math. Anal. Appl. 32 (1970), 274 – 307. · Zbl 0206.46504
[33]	F. Robert, M. Charnay, and F. Musy, Itérations chaotiques série-parallèle pour des équations non-linéaires de point fixe, Apl. Mat. 20 (1975), 1 – 38 (French, with Czech summary).
[34]	U. Schendel, Introduction to numerical methods for parallel computers, Ellis Horwood Series: Mathematics and its Applications, Ellis Horwood Ltd., Chichester; Halsted Press [John Wiley & Sons, Inc.], New York, 1984. Translated from the German by B. W. Conolly. · Zbl 0563.65001
[35]	P. Spiteri, Simulation d’exécutions parallèles pour la résolution d’inéquations variationnelles stationnaires, EDF Bull. Direction Études Rech. Sér. C Math. Inform. 1 (1983), 149 – 158 (French).
[36]	Pierre Spiteri, Parallel asynchronous algorithms for solving boundary value problems, Parallel algorithms & architectures (Luminy, 1986) North-Holland, Amsterdam, 1986, pp. 73 – 84. · Zbl 0614.65107
[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]	Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. · Zbl 0998.65505