Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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

Authors: Xue-Cheng Tai and Paul Tseng
Journal: Math. Comp. 71 (2002), 1105-1135
MSC (2000): Primary 65J10, 65M55, 65Y05; Secondary 65K10, 65N55
Published electronically: November 14, 2001
MathSciNet review: 1898747
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65J10, 65M55, 65Y05, 65K10, 65N55

Retrieve articles in all journals with MSC (2000): 65J10, 65M55, 65Y05, 65K10, 65N55

Additional Information

Xue-Cheng Tai
Affiliation: Department of Mathematics, University of Bergen, Johannes Brunsgate 12, 5007, Bergen, Norway

Paul Tseng
Affiliation: Department of Mathematics, Box 354350, University of Washington, Seattle, Washington 98195

Keywords: Convex minimization, space decomposition, asynchronous computation, convergence rate, domain decomposition, multigrid, obstacle problem
Received by editor(s): September 27, 2000
Published electronically: 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.
Article copyright: © Copyright 2001 American Mathematical Society