Mathematics of Computation

Convergence rate analysis of an asynchronous space decomposition method for convex minimization

Author(s): Xue-Cheng Tai; Paul Tseng.
Journal: Math. Comp. 71 (2002), 1105-1135.
MSC (2000): Primary 65J10, 65M55, 65Y05; Secondary 65K10, 65N55
Posted: November 14, 2001
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract: We analyze the convergence rate of an asynchronous space decomposition method for constrained convex minimization in a reflexive Banach space. This method includes as special cases parallel domain decomposition methods and multigrid methods for solving elliptic partial differential equations. In particular, the method generalizes the additive Schwarz domain decomposition methods to allow for asynchronous updates. It also generalizes the BPX multigrid method to allow for use as solvers instead of as preconditioners, possibly with asynchronous updates, and is applicable to nonlinear problems. Applications to an overlapping domain decomposition for obstacle problems are also studied. The method of this work is also closely related to relaxation methods for nonlinear network flow. Accordingly, we specialize our convergence rate results to the above methods. The asynchronous method is implementable in a multiprocessor system, allowing for communication and computation delays among the processors.

1.: L. Badea and J. Wang, An additive Schwarz method for variational inequalities, Math. Comp. 69 (2000), 1341-1354. MR 2001a:65075
2.: R. Bank, Analysis of a multilevel iterative method for nonlinear finite element equations, Math. Comp. 39 (1982), 453-465. MR 83j:65105
3.: R. Bank and T. F. Chan, PLTMGC: a multigrid continuation program for parametrized nonlinear systems, SIAM T. Sci. Statist. Comput., 7 (1986), 540-559. MR 87d:65125
4.: D. P. Bertsekas, D. Castañon, J. Eckstein, and S. A. Zenios, Parallel computing in network optimization, Handbooks in Operations Research and Management Science 7: Network Models (Amsterdam) (M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, eds.), Elsevier Scientific, 1995, pp. 331-399. CMP 97:04
5.: D. P. Bertsekas and J. N. Tsitsiklis, Parallel and distributed computation: Numerical methods, Prentice-Hall, Englewood Cliffs, 1989.
6.: -, Some aspects of parallel and distributed iterative algorithms--a survey, Automatica 27 (1991), 3-21. MR 91m:65137
7.: J. Bramble and X. Zhang, The analysis of multigrid methods, Handbook of numerical analysis, Vol. VII, 173-415, North-Holland, Amsterdam, 2000. CMP 2001:08
8.: J. H. Bramble, J. E. Pasciak, and A. H. Schatz, The construction of preconditioners for elliptic problems by substructuring. IV, Math. Comp. 53 (1989), 1-24.MR 89m:65098
9.: J. H. Bramble, J. E. Pasciak, J. Wang, and J. Xu, Convergence estimates for product iterative methods with applications to domain decomposition, Math. Comp. 57 (1991), 1-21. MR 92d:65094
10.: J. H. Bramble, J. E. Pasciak, and J. Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), 1-22. MR 90k:65170
11.: A. Brandt, Multilevel adaptive solutions to boundary value problems, Math. Comp. 31 (1977), 333-390. MR 55:4714
12.: A. Brandt and C. W. Cryer, Multigrid algorithms for the solution of linear complementary problems arising from free boundary problems, SIAM J. Sci. Comput. 4 (1983), 655-684. MR 85h:65261
13.: J. V. Burke and P. Tseng, A unified analysis of Hoffman's bound via Fenchel duality, SIAM J. Optim. 6 (1996), 265-282. MR 97c:90120
14.: T. F. Chan and T. P. Mathew, Domain decomposition algorithms, Acta Numerica (1994), 61-143. MR 95f:65214
15.: T. F. Chan and I. Sharapov, Subspace correction multilevel methods for elliptic eigenvalue problems, Numer. Linear Algebra Appl., 1 (1993), 1-7.
16.: D. Chazan and W. L. Miranker, Chaotic relaxation, Lin. Algeb. Appl. 2 (1969), 199-222. MR 40:5114
17.: P. G. Ciarlet, The finite element method for elliptic problems, North-Holland, Amsterdam, 1978. MR 58:25001
18.: M. Dryja and W. Hackbusch, On the nonlinear domain decomposition method, BIT 37 (1997), 296-311. MR 97m:65100
19.: M. Dryja and O. B. Widlund, Towards a unified theory of domain decomposition algorithms for elliptic problems, Third international symposium on domain decomposition methods for partial differential equations (Philadelphia, PA) (T. Chan, R. Glowinski, J. Periaux, and O. B. Widlund, eds.), SIAM, 1990. MR 91m:65294
20.: I. Ekeland and R. Temam, Convex analysis and variational problems, North-Holland, Amsterdam, 1976. MR 57:3931b
21.: B. H. Elton, An asynchronous domain decomposition method for the two-dimensional Poisson equation, Parallel processing for scientific computing, Vol. I, II (Norfolk, VA, 1993), SIAM, Philadelphia, PA, 1993, pp. 691-695. CMP 93:10
22.: A. Frommer, H. Schwandt, and D. B. Szyld, Asychronous weighted additive Schwarz methods, Electronic Trans. Numer. Anal. 5 (1997), 48-61. MR 98c:65046
23.: E. Gelman and J. Mandel, On multilevel iterative methods for optimization problems, Math. Programming 48 (1990), 1-17. MR 91b:90180
24.: R. Glowinski and P. Le Tallec, Augmented Lagrangian and operator-splitting methods in nonlinear mechanics, SIAM, Philadelphia, 1989. MR 91f:73038
25.: W. Hackbusch and H. D. Mittelmann, On multigrid methods for variational inequalities, Numer. Math. 42 (1983), 65-76. MR 84k:49010
26.: W. Hackbusch and A. Reusken, Analysis of a damped nonlinear multilevel method, Numer. Math. 55 (1989), 225-246. MR 90f:65194
27.: L. Hart and S. McCormick, Asynchronous multilevel adaptive methods for solving partial differential equations on multiprocessors: basic ideas, Parallel Comput. 12 (1989), no. 2, 131-144. MR 90m:65250
28.: R. H. Hoppe, Multigrid solutions to the elastic plastic torsion problem in multiply connected domains, Int. J. Numer. Methods Engin. 26 (1988), 631-646. MR 89a:73001
29.: R. H. W. Hoppe, Two-sided approximations for unilateral variational inequalities by multigrid methods, Optimization 16 (1987), 867-881. MR 88m:49004
30.: R. H. W. Hoppe and R. Kornhuber, Adaptive multilevel methods for obstacle problems, SIAM J. Numer. Anal. 31 (1994), 301-323. MR 95c:65181
31.: R. Kornhuber, Monotone multigrid iterations for elliptic variational inequalities, II, Numer. Math. 72 (1996), 481-499. MR 96k:65081
32.: O. A. Ladyzhenskaya and N. N. Uraltseva, Linear and quasilinear elliptic equations, Academic Press, 1968. MR 39:5941
33.: P. Le Tallec, Domain decomposition methods in computational mechanics, Comput. Mechan. Adv. 1 (1994), 121-220. MR 95b:65147
34.: Z.-Q. Luo and P. Tseng, On the linear convergence of descent methods for convex essentially smooth minimization, SIAM J. Control Optim. 30 (1992), 408-425. MR 93a:90064
35.: -, Error bounds and convergence analysis of feasible descent methods: A general approach, Ann. Oper. Res. 46 (1993), 157-178. MR 95a:90138
36.: J. Mandel, A multilevel iterative method for symmetric, positive definite linear complementary problems, Appl. Math. Optim. 11 (1984), 77-95.MR 85b:90082
37.: S. McCormick and D. Quinlan, Asynchronous multilevel adaptive methods for solving partial differential equations on multiprocessors: performance results, Parallel Comput. 12 (1989), no. 2, 145-156. MR 90m:65251
38.: S. F. McCormick, Multilevel adaptive methods for partial differential equations, Frontiers in Applied Mathematics, vol. 6, SIAM, Philadelphia, 1989.MR 91h:65200
39.: J.-C. Miellou, L. Giraud, A. Laouar, and P. Spiteri, Subdomain decomposition methods with overlapping and asynchronous iterations, Progress in partial differential equations: the Metz surveys, Longman Sci. Tech., Harlow, 1991, pp. 166-183. MR 94h:65125
40.: A. Quarteroni and A. Valli, Domain decomposition methods for partial differential equations, Oxford Science Publications, Oxford, 1999.
41.: R. Rannacher, On the convergence of the Newton-Raphson method for strongly nonlinear finite element equations, Nonlinear computational mechanics (P. Wriggers and W. Wagner, eds.), Springer-Verlag, 1991.
42.: R. T. Rockafellar, Convex analysis, Princeton University Press, Princeton, 1970. MR 43:445
43.: -, Network flows and monotropic optimization, Wiley-Interscience, New York, 1984.MR 89d:90156
44.: I. Sharapov, Multilevel subspace correction for large scale optimization problems, East-West J. Numer. Math., 9 (2000), 233-252.
45.: B. F. Smith, P. E. Bjørstad, and W. D. Gropp, Domain decomposition: Parallel multilevel algorithms for elliptic partial differential equations, Cambridge University Press, Cambridge, 1996. MR 98g:65003
46.: A. K. Stagg and G. F. Carey, Asynchronous nonlinear iteration and domain decomposition, Parallel processing for scientific computing (Houston, TX, 1991), SIAM, Philadelphia, PA, 1992, pp. 281-286. CMP 93:05
47.: X.-C. Tai, Parallel function decomposition and space decomposition methods with applications to optimisation, splitting and domain decomposition, Preprint No. 231-1992, Institut für Mathematik, TechnischeUniversität Graz (1992), See also http://www.mi.uib.no/ $\tilde{\;}$ tai.
48.: -, Parallel function and space decomposition methods, Finite element methods, fifty years of the Courant element, Lecture notes in pure and applied mathematics (P. Neittaanmäki, ed.), vol. 164, Marcel Dekker inc., 1994, pp. 421-432. See also http://www.mi.uib.no/ $\tilde{\;}$ tai. MR 95d:65008
49.: -, Domain decomposition for linear and nonlinear elliptic problems via function or space decomposition, Domain decomposition methods in scientific and engineering computing (Proc. of the 7th international conference on domain decomposition, Penn. State University, 1993) (D. Keyes and J. Xu, eds.), Contemp. Math. 180, American Mathematical Society, 1994, pp. 355-360. MR 95k:65121
50.: -, Parallel function decomposition and space decomposition methods: Part II. Space decomposition, Beijing Mathematics 1, part 2 (1995), 135-152, See also http://www.mi.uib.no/ $\tilde{\;}$ tai.
51.: -, Convergence rate analysis of domain decomposition methods for obstacle problems, East-West J. Numer. Math., 9 (2000), 233-253.
52.: X.-C. Tai and M. Espedal, Rate of convergence of some space decomposition method for linear and nonlinear elliptic problems, SIAM J. Numer. Anal. 35 (1998), 1558-1570. MR 99k:65101
53.: X-C. Tai and J.-C. Xu, Global and uniform convergence of subspace correction methods for some convex optimization problems, Math. Comp., posted on May 11, 2001, PII S0025-5718(01)01311-4 (to appear in print).
54.: M. Tinkham, Introduction to superconductivity, McGraw Hill, New York, 1975.
55.: P. Tseng, On the rate of convergence of a partially asynchronous gradient projection algorithm, SIAM J. Optim. 1 (1991), 603-619. MR 92k:90096
56.: P. Tseng, D. P. Bertsekas, and J. N. Tsitsiklis, Partially asynchronous, parallel algorithms for network flow and other problems, SIAM J. Control Optim. 28 (1990), 678-710. MR 91e:65075
57.: J.-C. Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), 581-613. MR 93k:65029
58.: -, A novel two-grid method for semilinear elliptic equations, SIAM J. Sci. Comp. 15 (1994), 231-237. MR 94m:65178
59.: -, Two-grid discretization techniques for linear and nonlinear PDEs, SIAM J. Numer. Anal. 27 (1996), 1759-1777. MR 97i:65169
60.: J. Zeng and S. Zhou, On monotone and geometric convergence of Schwarz methods for two-sided obstacle problems, SIAM J. Numer. Anal. 35 (1998), 600-616. MR 99d:65199

Xue-Cheng Tai
Affiliation: Department of Mathematics, University of Bergen, Johannes Brunsgate 12, 5007, Bergen, Norway
Email: Xue-Cheng.Tai@mi.uib.no

Paul Tseng
Affiliation: Department of Mathematics, Box 354350, University of Washington, Seattle, Washington 98195
Email: tseng@math.washington.edu

DOI: 10.1090/S0025-5718-01-01344-8
PII: S 0025-5718(01)01344-8
Keywords: Convex minimization, space decomposition, asynchronous computation, convergence rate, domain decomposition, multigrid, obstacle problem
Received by editor(s): September 27, 2000
Posted: November 14, 2001
Additional Notes: The work of the first author was supported by the Norwegian Research Council Strategic Institute Program within Inverse Problems at RF-Rogaland Research, and by Project SEP-115837/431 at Mathematics Institute, University of Bergen.
The work of the second author was supported by the National Science Foundation, Grant No. CCR-9311621.
Copyright of article: Copyright 2001, 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