{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:38:41Z","timestamp":1776728321271,"version":"3.51.2"},"reference-count":60,"publisher":"American Mathematical Society (AMS)","issue":"239","license":[{"start":{"date-parts":[[2002,11,14]],"date-time":"2002-11-14T00:00:00Z","timestamp":1037232000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>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.<\/p>","DOI":"10.1090\/s0025-5718-01-01344-8","type":"journal-article","created":{"date-parts":[[2002,9,20]],"date-time":"2002-09-20T15:46:54Z","timestamp":1032536814000},"page":"1105-1135","source":"Crossref","is-referenced-by-count":31,"title":["Convergence rate analysis of an asynchronous space decomposition method for convex Minimization"],"prefix":"10.1090","volume":"71","author":[{"given":"Xue-Cheng","family":"Tai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Tseng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2001,11,14]]},"reference":[{"issue":"232","key":"1","doi-asserted-by":"publisher","first-page":"1341","DOI":"10.1090\/S0025-5718-99-01164-3","article-title":"An additive Schwarz method for variational inequalities","volume":"69","author":"Badea, Lori","year":"2000","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"160","key":"2","doi-asserted-by":"publisher","first-page":"453","DOI":"10.2307\/2007324","article-title":"Analysis of a multilevel iterative method for nonlinear finite element equations","volume":"39","author":"Bank, Randolph E.","year":"1982","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/0907036","article-title":"PLTMGC: a multigrid continuation program for parameterized nonlinear elliptic systems","volume":"7","author":"Bank, Randolph E.","year":"1986","journal-title":"SIAM J. Sci. Statist. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-5204","issn-type":"print"},{"key":"4","doi-asserted-by":"crossref","unstructured":"D. P. Bertsekas, D. Casta\u00f1on, 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\u2013399.","DOI":"10.1016\/S0927-0507(05)80122-7"},{"key":"5","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis, Parallel and distributed computation: Numerical methods, Prentice-Hall, Englewood Cliffs, 1989."},{"issue":"1","key":"6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0005-1098(91)90003-K","article-title":"Some aspects of parallel and distributed iterative algorithms\u2014a survey","volume":"27","author":"Bertsekas, Dimitri P.","year":"1991","journal-title":"Automatica J. IFAC","ISSN":"https:\/\/id.crossref.org\/issn\/0005-1098","issn-type":"print"},{"key":"7","doi-asserted-by":"crossref","unstructured":"J. Bramble and X. Zhang, The analysis of multigrid methods, Handbook of numerical analysis, Vol. VII, 173\u2013415, North-Holland, Amsterdam, 2000.","DOI":"10.1016\/S1570-8659(00)07003-4"},{"issue":"187","key":"8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2008346","article-title":"The construction of preconditioners for elliptic problems by substructuring. IV","volume":"53","author":"Bramble, James H.","year":"1989","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"195","key":"9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2938660","article-title":"Convergence estimates for product iterative methods with applications to domain decomposition","volume":"57","author":"Bramble, James H.","year":"1991","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"191","key":"10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2008789","article-title":"Parallel multilevel preconditioners","volume":"55","author":"Bramble, James H.","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"138","key":"11","doi-asserted-by":"publisher","first-page":"333","DOI":"10.2307\/2006422","article-title":"Multi-level adaptive solutions to boundary-value problems","volume":"31","author":"Brandt, Achi","year":"1977","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"12","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1137\/0904046","article-title":"Multigrid algorithms for the solution of linear complementarity problems arising from free boundary problems","volume":"4","author":"Brandt, Achi","year":"1983","journal-title":"SIAM J. Sci. Statist. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-5204","issn-type":"print"},{"issue":"2","key":"13","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1137\/0806015","article-title":"A unified analysis of Hoffman\u2019s bound via Fenchel duality","volume":"6","author":"Burke, James V.","year":"1996","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"key":"14","isbn-type":"print","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1017\/S0962492900002427","article-title":"Domain decomposition algorithms","author":"Chan, Tony F.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0521461812"},{"key":"15","doi-asserted-by":"crossref","unstructured":"T. F. Chan and I. Sharapov, Subspace correction multilevel methods for elliptic eigenvalue problems, Numer. Linear Algebra Appl., 1 (1993), 1\u20137.","DOI":"10.1002\/nla.238"},{"key":"16","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0024-3795(69)90028-7","article-title":"Chaotic relaxation","volume":"2","author":"Chazan, D.","year":"1969","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"17","series-title":"Studies in Mathematics and its Applications, Vol. 4","isbn-type":"print","volume-title":"The finite element method for elliptic problems","author":"Ciarlet, Philippe G.","year":"1978","ISBN":"https:\/\/id.crossref.org\/isbn\/0444850287"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/BF02510214","article-title":"On the nonlinear domain decomposition method","volume":"37","author":"Dryja, M.","year":"1997","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"key":"19","isbn-type":"print","first-page":"3","article-title":"Towards a unified theory of domain decomposition algorithms for elliptic problems","author":"Dryja, Maksymilian","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/089871253X"},{"key":"20","series-title":"Collection \\'{E}tudes Math\\'{e}matiques","volume-title":"Analyse convexe et probl\\`emes variationnels","author":"Ekeland, Ivar","year":"1974"},{"key":"21","unstructured":"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\u2013695."},{"key":"22","first-page":"48","article-title":"Asynchronous weighted additive Schwarz methods","volume":"5","author":"Frommer, Andreas","year":"1997","journal-title":"Electron. Trans. Numer. Anal."},{"issue":"1","key":"23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01582249","article-title":"On multilevel iterative methods for optimization problems","volume":"48","author":"Gelman, E.","year":"1990","journal-title":"Math. Programming","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"24","series-title":"SIAM Studies in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970838","volume-title":"Augmented Lagrangian and operator-splitting methods in nonlinear mechanics","volume":"9","author":"Glowinski, Roland","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0898712300"},{"issue":"1","key":"25","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01400918","article-title":"On multigrid methods for variational inequalities","volume":"42","author":"Hackbusch, W.","year":"1983","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"2","key":"26","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF01406516","article-title":"Analysis of a damped nonlinear multilevel method","volume":"55","author":"Hackbusch, W.","year":"1989","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"2","key":"27","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0167-8191(89)90048-3","article-title":"Asynchronous multilevel adaptive methods for solving partial differential equations on multiprocessors: basic ideas","volume":"12","author":"Hart, L.","year":"1989","journal-title":"Parallel Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-8191","issn-type":"print"},{"issue":"3","key":"28","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1002\/nme.1620260308","article-title":"Multigrid solutions to the elastic plastic torsion problem in multiply connected domains","volume":"26","author":"Hoppe, Ronald H. W.","year":"1988","journal-title":"Internat. J. Numer. Methods Engrg.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-5981","issn-type":"print"},{"issue":"6","key":"29","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1080\/02331938708843301","article-title":"Two-sided approximations for unilateral variational inequalities by multigrid methods","volume":"18","author":"Hoppe, R. H. W.","year":"1987","journal-title":"Optimization","ISSN":"https:\/\/id.crossref.org\/issn\/0233-1934","issn-type":"print"},{"issue":"2","key":"30","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1137\/0731016","article-title":"Adaptive multilevel methods for obstacle problems","volume":"31","author":"Hoppe, R. H. W.","year":"1994","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"4","key":"31","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/s002110050178","article-title":"Monotone multigrid methods for elliptic variational inequalities. II","volume":"72","author":"Kornhuber, Ralf","year":"1996","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"32","volume-title":"Linear and quasilinear elliptic equations","author":"Ladyzhenskaya, Olga A.","year":"1968"},{"issue":"2","key":"33","first-page":"121","article-title":"Domain decomposition methods in computational mechanics","volume":"1","author":"Le Tallec, Patrick","year":"1994","journal-title":"Comput. Mech. Adv.","ISSN":"https:\/\/id.crossref.org\/issn\/0927-7951","issn-type":"print"},{"issue":"2","key":"34","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1137\/0330025","article-title":"On the linear convergence of descent methods for convex essentially smooth minimization","volume":"30","author":"Luo, Zhi-Quan","year":"1992","journal-title":"SIAM J. Control Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/0363-0129","issn-type":"print"},{"issue":"1-4","key":"35","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02096261","article-title":"Error bounds and convergence analysis of feasible descent methods: a general approach","volume":"46\/47","author":"Luo, Zhi-Quan","year":"1993","journal-title":"Ann. Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0254-5330","issn-type":"print"},{"issue":"1","key":"36","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF01442171","article-title":"A multilevel iterative method for symmetric, positive definite linear complementarity problems","volume":"11","author":"Mandel, Jan","year":"1984","journal-title":"Appl. Math. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/0095-4616","issn-type":"print"},{"issue":"2","key":"37","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0167-8191(89)90049-5","article-title":"Asynchronous multilevel adaptive methods for solving partial differential equations on multiprocessors: performance results","volume":"12","author":"McCormick, S.","year":"1989","journal-title":"Parallel Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-8191","issn-type":"print"},{"issue":"4","key":"38","first-page":"121","article-title":"Numerical solution of elliptic problems of order 2\ud835\udc5a by the method of least squares using spline approximation on rectangular grids","volume":"2","author":"Marchenko, N. A.","year":"1990","journal-title":"Mat. Model.","ISSN":"https:\/\/id.crossref.org\/issn\/0234-0879","issn-type":"print"},{"key":"39","isbn-type":"print","first-page":"166","article-title":"Subdomain decomposition methods with overlapping and asynchronous iterations","author":"Miellou, J.-C.","year":"1991","ISBN":"https:\/\/id.crossref.org\/isbn\/0582070244"},{"key":"40","doi-asserted-by":"crossref","unstructured":"A. Quarteroni and A. Valli, Domain decomposition methods for partial differential equations, Oxford Science Publications, Oxford, 1999.","DOI":"10.1093\/oso\/9780198501787.001.0001"},{"key":"41","unstructured":"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."},{"key":"42","series-title":"Princeton Mathematical Series, No. 28","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex analysis","author":"Rockafellar, R. Tyrrell","year":"1970"},{"issue":"1","key":"43","first-page":"15","article-title":"The determination of saddle points","volume":"43","author":"Abasov, T. M.","year":"1987","journal-title":"Akad. Nauk Azerba\\u{\\i}dzhan. SSR Dokl.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-3078","issn-type":"print"},{"key":"44","unstructured":"I. Sharapov, Multilevel subspace correction for large scale optimization problems, East-West J. Numer. Math., 9 (2000), 233\u2013252."},{"key":"45","isbn-type":"print","volume-title":"Domain decomposition","author":"Smith, Barry F.","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/052149589X"},{"key":"46","unstructured":"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\u2013286."},{"key":"47","unstructured":"X.-C. Tai, Parallel function decomposition and space decomposition methods with applications to optimisation, splitting and domain decomposition, Preprint No. 231\u20131992, Institut f\u00fcr Mathematik, TechnischeUniversit\u00e4t Graz (1992), See also http:\/\/www.mi.uib.no\/\u02dctai."},{"key":"48","series-title":"Lecture Notes in Pure and Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1201\/b16924","volume-title":"Finite element methods","volume":"164","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0824792769"},{"key":"49","isbn-type":"print","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1090\/conm\/180\/01992","article-title":"Domain decomposition for linear and nonlinear elliptic problems via function or space decomposition","author":"Tai, Xue Cheng","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0821851713"},{"key":"50","unstructured":"\\bysame, Parallel function decomposition and space decomposition methods: Part II. Space decomposition, Beijing Mathematics 1, part 2 (1995), 135\u2013152, See also http:\/\/www.mi.uib.no\/\u02dctai."},{"key":"51","doi-asserted-by":"crossref","unstructured":"\\bysame, Convergence rate analysis of domain decomposition methods for obstacle problems, East-West J. Numer. Math., 9 (2000), 233\u2013253.","DOI":"10.1515\/JNMA.2001.233"},{"issue":"4","key":"52","doi-asserted-by":"publisher","first-page":"1558","DOI":"10.1137\/S0036142996297461","article-title":"Rate of convergence of some space decomposition methods for linear and nonlinear problems","volume":"35","author":"Tai, Xue-Cheng","year":"1998","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"53","unstructured":"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)."},{"key":"54","unstructured":"M. Tinkham, Introduction to superconductivity, McGraw Hill, New York, 1975."},{"issue":"4","key":"55","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1137\/0801036","article-title":"On the rate of convergence of a partially asynchronous gradient projection algorithm","volume":"1","author":"Tseng, Paul","year":"1991","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"3","key":"56","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1137\/0328040","article-title":"Partially asynchronous, parallel algorithms for network flow and other problems","volume":"28","author":"Tseng, P.","year":"1990","journal-title":"SIAM J. Control Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/0363-0129","issn-type":"print"},{"issue":"4","key":"57","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1137\/1034116","article-title":"Iterative methods by space decomposition and subspace correction","volume":"34","author":"Xu, Jinchao","year":"1992","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"1","key":"58","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1137\/0915016","article-title":"A novel two-grid method for semilinear elliptic equations","volume":"15","author":"Xu, Jinchao","year":"1994","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"5","key":"59","doi-asserted-by":"publisher","first-page":"1759","DOI":"10.1137\/S0036142992232949","article-title":"Two-grid discretization techniques for linear and nonlinear PDEs","volume":"33","author":"Xu, Jinchao","year":"1996","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"2","key":"60","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1137\/S0036142995288920","article-title":"On monotone and geometric convergence of Schwarz methods for two-sided obstacle problems","volume":"35","author":"Zeng, Jinping","year":"1998","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2002-71-239\/S0025-5718-01-01344-8\/S0025-5718-01-01344-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2002-71-239\/S0025-5718-01-01344-8\/S0025-5718-01-01344-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:00:30Z","timestamp":1776726030000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2002-71-239\/S0025-5718-01-01344-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,11,14]]},"references-count":60,"journal-issue":{"issue":"239","published-print":{"date-parts":[[2002,7]]}},"alternative-id":["S0025-5718-01-01344-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-01-01344-8","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2001,11,14]]}}}