On the convergence rate of a parallel nonoverlapping domain decomposition method

In recent years,a nonoverlapping domain decomposition iterative procedure,which is based on using Robin-type boundary conditions as information transmission conditions on the subdomain interfaces,has been developed and analyzed.It is known that the convergence rate of this method is 1-O(h),where h is mesh size.In this paper,the convergence rate is improved to be 1-O(h1/2 H-1/2)sometime by choosing suitable parameter,where H is the subdomain size.Counter examples are constructed to show that our convergence estimates are sharp,which means that the convergence rate cannot be better than 1-O(h1/2H-1/2)in a certain case no matter how parameter is chosen.     

A parallel finite element variational multiscale method based on fully overlapping domain decomposition for incompressible flows

Based on fully overlapping domain decomposition and a recent variational multiscale method, a parallel finite element variational multiscale method for convection dominated incompressible flows is proposed and analyzed. In this method, each processor computes a local finite element solution in its own subdomain using a global mesh that is locally refined around its own subdomain, where a stabilization term based on two local Gauss integrations is adopted to stabilize the numerical form of the Navier–Stokes equations. Using the technical tool of local a priori estimate for the finite element solution, error bounds of the discrete solution are estimated. Algorithmic parameter scalings are derived. Numerical tests are also given to verify the theoretical predictions and demonstrate the effectiveness of the method. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 856–875, 2015     

A parallel iterative nonoverlapping domain decomposition procedure for elliptic problems

E-mail: yangd{at}math.purdue.edu or yangd{at}cs.purdue.edu Present address: Department of Mathematics Wayne State University, Detroit, MI 48202, USA. A parallel iterative nonoverlapping domain decomposition methodis proposed and analyzed for elliptic problems. Each iterationin this method contains two steps. In the first step, at theinterface of two subdomains, one subdomain problem requiresthat Dirichlet data be passed to it from the previous iterationlevel, while the other subdomain problem requires that Neumamdata be passed to it. In the second step, we interchange thetypes of data passing at the interface of the two subdomains.This domain decomposition method is suitable for parallel processingwith coarse granularity. Convergence analysis is demonstratedat the differential level by Hilbert space techniques. Numericalresults are provided to confirm the convergence theory.     

A parallel radix‐4 block cyclic reduction algorithm

A conventional block cyclic reduction algorithm operates by halving the size of the linear system at each reduction step, that is, the algorithm is a radix‐2 method. An algorithm analogous to the block cyclic reduction known as the radix‐q partial solution variant of the cyclic reduction (PSCR) method allows the use of higher radix numbers and is thus more suitable for parallel architectures as it requires fever reduction steps. This paper presents an alternative and more intuitive way of deriving a radix‐4 block cyclic reduction method for systems with a coefficient matrix of the form tridiag{ ? I,D, ? I}. This is performed by modifying an existing radix‐2 block cyclic reduction method. The resulting algorithm is then parallelized by using the partial fraction technique. The parallel variant is demonstrated to be less computationally expensive when compared to the radix‐2 block cyclic reduction method in the sense that the total number of emerging subproblems is reduced. The method is also shown to be numerically stable and equivalent to the radix‐4 PSCR method. The numerical results archived correspond to the theoretical expectations. Copyright © 2013 John Wiley & Sons, Ltd.     

A note on augmented Lagrangian-based parallel splitting method

We consider the linearly constrained separable convex minimization problem, whose objective function consists of the sum of \(m\) individual convex functions in the absence of any coupling variables. While augmented Lagrangian-based decomposition methods have been well developed in the literature for solving such problems, a noteworthy requirement of these methods is that an additional correction step is a must to guarantee their convergence. This note shows that a straightforward Jacobian decomposition of the augmented Lagrangian method is globally convergent if the involved functions are further assumed to be strongly convex.     

A reduction method for variational inequalities

This paper explains a method by which the number of variables in a variational inequality having a certain form can be substantially reduced by changing the set over which the variational inequality is posed. The method applies in particular to certain economic equilibrium problems occurring in applications. We explain and justify the method, and give examples of its application, including a numerical example in which the solution time for the reduced problem was approximately 2% of that for the problem in its original form. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.The research reported here was sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number F49620-95-1-0222, and by the U.S. Army Research Office under grant number DAAH04-95-1-0149. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the author and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the sponsoring agencies or the U.S. Government.     

A new parallel method for verified global optimization

We present a new parallel method for verified global optimization, using challenge leadership for the dynamic load balancing. The new approach combines advantages of two previous models: the centralized mediator model (see [1]) and the processor farm (see [2]). It has the following properties: centralization of the process; reduction of the number of box exchanges, communications used to send boxes from one processor to another; handling of the box that most probably contains the global minimizer. Numerical results show the efficiency of this method.     

A hybrid graph-genetic method for domain decomposition

A new method is developed for finite element (FE) domain decomposition. This method employs a hybrid graph-genetic algorithm for graph partitioning and correspondingly bisects finite element (FE) meshes.

A weighted incidence graph is first constructed for the FE mesh, denoted by G₀. A coarsening process is then performed using heavy-edge matching. A sequence of such operations is employed in “n” steps, which leads to the formation of G_n with a size suitable for genetic algorithm applications.

Hereafter, G_n is bisected using conventional genetic algorithm. The shortest route tree algorithm is used for the formation of the initial population in genetic algorithm. Then an uncoarsening process is performed and the results are transferred to the graph G_n−1. The initial population for genetic algorithm on G_n−1is constructed from the results of G_n. This process is repeated until G₀ is obtained in the uncoarsening operation. Employing the properties of G₁, the graph G₀ is bisected by the genetic algorithm.     

Error reduction for higher derivatives of Chebyshev collocation method using preconditioning and domain decomposition

A new preconditioning method is investigated to reduce the roundoff error in computing derivatives using Chebyshev collocation methods(CCM). Using this preconditioning causes ratio of roundoff error of preconditioning method and CCM becomes small when N gets large. Also for accuracy enhancement of differentiation we use a domain decomposition approach. Error analysis shows that for this domain decomposition method error reduces proportional to the length of subintervals. Numerical results show that using domain decomposition and preconditioning simultaneously, gives super accurate approximate values for first derivative of the function and good approximate values for moderately high derivatives.     

A parallel implementation of overlapping Schwarz method for the dual reciprocity method

We present a parallel algorithm for the overlapping domain decomposition boundary integral equation method for two dimensional partial differential equations. In addition to the improvement of the ill-conditioning and the computational efficiency achieved by domain partitioning, using a parallel computer with p processors can offer up to p times efficiency. Assuming direct solution is used throughout, partitioning the domain into p subregions and employing a processor for each subproblem, overall, result in p² times efficiency over using a single domain and a single processor, taking into account that a sequential algorithm of the underlying method can improve the computational efficiency at least p times over using a single domain. Some numerical results showing the efficiency of the parallel technique will be presented.     

A mixed forward-backward dynamic programming method using parallel computation

We consider optimization problems which can be solved by either forward or backward dynamic programming. We propose a method which reduces the computing time by a factor of two when two processors are used in parallel.This research was sponsored by the National Science Foundation, Grant No. INT-78-09263, while the author was visiting at the University of California, Berkeley, California.     

A new reduction method in integer programming

The system of two equations in nonnegative integer unknowns x_j and expressed in the form ∑ⁿ_j=1 a_1jx_j=b₁, ∑ⁿ_j=1 a_2jx_j=b₂ has equivalent solutions to the single equation ∑ⁿ_j=1 (t₁a_ij+t₂a_2j)a_j= t₁b₁+t₂b₂, provided t₁ and t₂ are suitably chosen. Glover [2] has n inequalities for determining t₁ and t₂. Elimam and Elmaghraby [1] try to achieve a single inequality for t₁ and t₂. We show, however, that the inequality of [1] may give t₁ and t₂ values that do not produce equivalence. We present a new theorem which leads to a single inequality constraint giving t₁ and t₂ values that consistently produce equivalence.     

A new fictitious domain method in shape optimization

The present paper is concerned with investigating the capability of the smoothness preserving fictitious domain method from Mommer (IMA J. Numer. Anal. 26:503–524, 2006) to shape optimization problems. We consider the problem of maximizing the Dirichlet energy functional in the class of all simply connected domains with fixed volume, where the state equation involves an elliptic second order differential operator with non-constant coefficients. Numerical experiments in two dimensions validate that we arrive at a fast and robust algorithm for the solution of the considered class of problems. The proposed method can be applied to three dimensional shape optimization problems.     

A domain decomposition method based on the iterative operator splitting method

In this article a new approach is proposed for constructing a domain decomposition method based on the iterative operator splitting method. The convergence properties of such a method are studied. The main feature of the proposed idea is the decoupling of space and time. We present a multi-iterative operator splitting method that combines iteratively the space and time splitting. We confirm with numerical applications the effectiveness of the proposed iterative operator splitting method in comparison with the classical Schwarz waveform relaxation method as a standard method for domain decomposition. We provide improved results and convergence rates.     

A hybrid domain decomposition method based on aggregation

A new two‐level black‐box preconditioner based on the hybrid domain decomposition technique is proposed and studied. The preconditioner is a combination of an additive Schwarz preconditioner and a special smoother. The smoother removes dependence of the condition number on the number of subdomains and variations of the diffusion coefficient and leaves minor sensitivity to the problem size. The algorithm is parallel and pure algebraic which makes it a convenient framework for the construction parallel black‐box preconditioners on unstructured meshes. Copyright © 2004 John Wiley & Sons, Ltd.     

A regularized domain decomposition method with Lagrange multiplier

In this paper, we are concerned with the nonoverlapping domain decomposition method with Lagrange multiplier for three-dimensional second-order elliptic problems with no zeroth-order term. It is known that the methods result in a singular subproblem on each internal (floating) subdomain. To handle the singularity, we propose a regularization technique which transforms the corresponding singular problems into approximate positive definite problems. For the regularized method, one can build the interface equation of the multiplier directly. We first derive an optimal error estimate of the regularized approximation, and then develop a cheap preconditioned iterative method for solving the interface equation. For the new method, the cost of computation will not be increased comparing the case without any floating subdomain. The effectiveness of the new method will be confirmed by both theoretical analyzes and numerical experiments. The work is supported by Natural Science Foundation of China G10371129.     

A domain decomposition method using efficient interface-acting preconditioners

The conjugate gradient boundary iteration (CGBI) is a domain decomposition method for symmetric elliptic problems on domains with large aspect ratio. High efficiency is reached by the construction of preconditioners that are acting only on the subdomain interfaces. The theoretical derivation of the method and some numerical results revealing a convergence rate of 0.04-0.1 per iteration step are given in this article. For the solution of the local subdomain problems, both finite element (FE) and spectral Chebyshev methods are considered.

     

A mixed directed-undirected data structure for a parallel implementation of a domain decomposition algorithm

The choice of data structures influences the parallelization, efficiency and the manageability of a mesh refinement program. We introduce a mixed directed-undirected graph that combines both communication and scheduling needs. An inverted index is maintained for the directed graph to improve code performance and readability.This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48.     

A parallel projection method for solving generalized linear least-squares problems

Summary A parallel projection algorithm is proposed to solve the generalized linear least-squares problem: find a vector to minimize the 2-norm distance from its image under an affine mapping to a closed convex cone. In each iteration of the algorithm the problem is decomposed into several independent small problems of finding projections onto subspaces, which are simple and can be tackled parallelly. The algorithm can be viewed as a dual version of the algorithm proposed by Han and Lou [8]. For the special problem under consideration, stronger convergence results are established. The algorithm is also related to the block iterative methods of Elfving [6], Dennis and Steihaug [5], and the primal-dual method of Springarn [14].This material is based on work supported in part by the National Science foundation under Grant DMS-8602416 and by the Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign