Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A new class of asynchronous iterative algorithms with order intervals
HTML articles powered by AMS MathViewer

by J. C. Miellou, D. El Baz and P. Spiteri PDF
Math. Comp. 67 (1998), 237-255 Request permission

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.
References
  • 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. MR 1221041, DOI 10.1016/0167-8191(93)90003-4
  • R. H. Barlow and D. J. Evans, Synchronous and asynchronous iterative parallel algorithms for linear systems, Comput. J. 25 (1982), 56–60.
  • Gérard M. Baudet, Asynchronous iterative methods for multiprocessors, J. Assoc. Comput. Mach. 25 (1978), no. 2, 226–244. MR 494894, DOI 10.1145/322063.322067
  • Dimitri P. Bertsekas, Distributed dynamic programming, IEEE Trans. Automat. Control 27 (1982), no. 3, 610–616. MR 680319, DOI 10.1109/TAC.1982.1102980
  • Dimitri P. Bertsekas, Distributed asynchronous computation of fixed points, Math. Programming 27 (1983), no. 1, 107–120. MR 712113, DOI 10.1007/BF02591967
  • 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. MR 872452, DOI 10.1137/0325006
  • D. P. Bertsekas and J. Tsitsiklis, Parallel and distributed computation, Numerical Methods, Englewood Cliffs, Prentice Hall, 1989.
  • D. Chazan and W. Miranker, Chaotic relaxation, Linear Algebra Appl. 2 (1969), 199–222. MR 251888, DOI 10.1016/0024-3795(69)90028-7
  • 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).
  • Didier El Baz, $M$-functions and parallel asynchronous algorithms, SIAM J. Numer. Anal. 27 (1990), no. 1, 136–140. MR 1034924, DOI 10.1137/0727008
  • D. El Baz, Asynchronous gradient algorithms for a class of convex separable network flow problems, Computational Optimization and Applications 5 (1996), 187–205.
  • D. El Baz, Asynchronous implementation of relaxation and gradient algorithms for convex network flow problems, Parallel Computing 19 (1993), 1019–1028.
  • D. El Baz, Nonlinear systems of equations and parallel asynchronous iterative algorithms, Advances in Parallel Computing 9, North-Holland, Amsterdam, 1994, 89–96.
  • 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.
  • Mouhamed Nabih El Tarazi, Some convergence results for asynchronous algorithms, Numer. Math. 39 (1982), no. 3, 325–340 (French, with English summary). MR 678738, DOI 10.1007/BF01407866
  • Mouhamed Nabih El Tarazi, Algorithmes mixtes asynchrones. Étude de convergence monotone, Numer. Math. 44 (1984), no. 3, 363–369 (French, with English summary). MR 757492, DOI 10.1007/BF01405568
  • 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. MR 1123007, DOI 10.1016/S0167-8191(05)80103-6
  • Andreas Frommer, On asynchronous iterations in partially ordered spaces, Numer. Funct. Anal. Optim. 12 (1991), no. 3-4, 315–325. MR 1143002, DOI 10.1080/01630569108816431
  • 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). MR 1354647, DOI 10.1016/0377-0427(94)00083-D
  • 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). MR 1111656, DOI 10.1051/m2an/1991250505791
  • 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.
  • R. W. Hockney and C. R. Jesshope, Parallel Computers 2, Adam Hilger, Bristol, 1988.
  • 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). MR 596541, DOI 10.1051/m2an/1980140403691
  • Jean-Claude Miellou, Itérations chaotiques à retards, C. R. Acad. Sci. Paris Sér. A 278 (1974), 957–960 (French). MR 362887
  • 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). MR 391499
  • J. C. Miellou, Algorithmes de rélaxation chaotique à retards, Rev. Française Automat. Informat. Recherche Operationnelle Sér. 9 (1975), no. R-1, 55–82. MR 0440904
  • Jean-Claude Miellou, Asynchronous iterations and order intervals, Parallel algorithms & architectures (Luminy, 1986) North-Holland, Amsterdam, 1986, pp. 85–96. MR 875491
  • 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.
  • 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). MR 826228, DOI 10.1051/m2an/1985190406451
  • James M. Ortega, Introduction to parallel and vector solution of linear systems, Frontiers of Computer Science, Plenum Press, New York, 1989. MR 1106195
  • J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
  • Werner C. Rheinboldt, On $M$-functions and their application to nonlinear Gauss-Seidel iterations and to network flows, J. Math. Anal. Appl. 32 (1970), 274–307. MR 269101, DOI 10.1016/0022-247X(70)90298-2
  • 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). MR 373272
  • 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. MR 833290
  • 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). MR 700279
  • Pierre Spiteri, Parallel asynchronous algorithms for solving boundary value problems, Parallel algorithms & architectures (Luminy, 1986) North-Holland, Amsterdam, 1986, pp. 73–84. MR 875490
  • 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).
  • Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502
Similar Articles
Additional Information
  • 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
  • Received by editor(s): December 9, 1994
  • Received by editor(s) in revised form: January 26, 1996, and July 19, 1996
  • © Copyright 1998 American Mathematical Society
  • Journal: Math. Comp. 67 (1998), 237-255
  • MSC (1991): Primary 65N12, 65N55, 68Q10, 68Q22
  • DOI: https://doi.org/10.1090/S0025-5718-98-00885-0
  • MathSciNet review: 1432131