Domain Decomposition Methods

E-mail to Max Gunzburger

Collaborators

Description

Our approach to domain decomposition begins in the usual way. We subdivide the computational domain into nonoverlapping subdomains. The subdomains may be artifically introduced or may occur naturally in the problem. The subdomain problems are, in general, underdetermined in the sense that they contain unkown data. The crux of our method is a constrained minimization problem for which the objective functional measures the jump in the dependent variables across the common boundaries between subdomains; the minimization is effected with respect to unknown data along those same boundaries; the constraints are the subdomain boundary value problems for the partial differential equations. Here, we briefly describe our approach as it applies to linear problems, nonlinear problems, multidisciplinary problems, and optimization problems. Details are found in the papers cited below.

Linear problems

Suppose we are solving the Poisson equation in a square with a Dirichlet boundary condition imposed along the boundary of the square. We subdivide the square into smaller squares and impose a boundary condition along the interfaces between the subdomains. We may impose either a Dirichlet of Neumann condition; for the sake of concreteness, let us say we impose Neumann conditions along the interfaces. Of course, we do not know the data for these boundary conditions so that our task is to determine that data. If we impose incorrect Neumann data, then the solution of our subdomain problems will not be continuous across the interfaces. Thus, we determine the correct Neumann data by minimizing the jump in the solution of the subdomain problems across their common interfaces, with the Poisson problems in each subdomain acting as constraints on the minimization problem.

There are many choices available to us in the above strategy. First, we could have instead chosen Dirichlet boundary conditions along the interfaces and then minimized the jumps in the normal derivative across the interfaces. Second, we have a choice in what norm we will measure the jumps across the interfaces. Each combination of different norm and different boundary condition along the interface results in a different method. A number of known domain decomposition methods can be shown to be equivalent to our method with a particular choice of norm and interface condition. In addition, some choices evidently result in new methods.

We have analyzed our domain decomposition strategy for a number of different ways of solving the optimization problem. These include a Lagrange multiplier approach for enforcing the contraints, a least-squares approach, and a gradient method approach. In addition, we have implemented some of the methods and provided the results of some computational experiments.

Nonlinear problems

One of the nice features of the optimization-based domain decomposition approach is that it extends easily, from the algorithmic and even from the analysis viewpoints, to nonlinear problems. The reason for this is that the nonlinearities in the differential equation system appear in the contraints of the optimization problem; the objective functionals used in the optimization problem remain essentially unchanged from those of the linear setting.

We have examined our approach in the context of the Navier-Stokes equations. Here, Nuemann boundary condition involve the stress vector, but otherwise, other than we now have to deal with nonlinear constraints, everything proceeds as in the linear setting. We have analyzed and implemented optimization-based domain decomposition algorithms for the Navier-Stokes equations, giving, among other results, rigorous convergence results in this nonlinear setting.

Multidisciplinary problems

Many of the domain decomposition methods that can be designed using the optimzation-based approach are not useful for massively parallel computing because the convergence rate depends adversely on the number of subdomains. (Some of the methods, however, are indeed useful in that context.) However, any of the methods may be useful in the context of multidisciplinary problems, or even in the simpler case of a single discipline with model changes due to, e.g., discontinuous media properties. In this context, the number of subdomains is usually small so that we do not have to worry about convergence deterioration due to a large number of subdomains.

The usefulness of our approach for multidisciplinary problems stems from the flexibility we have in choosing the interface conditions; this was alluded to above when we discussed the application of our methods to linear problems. Let's expand on this a little. Suppose one wants to solve a multidisciplinary problem; for the sake of concreteness, let us choose the two discipline fluid-structure interaction problem. Suppose also that one has available good codes for separately solving each disciplinary problem, e.g., a good CFD code and a good structures code. One would like to use these codes, with little of no modification to them, to solve the multidisciplinary problem. Since we do not want to change either the CFD or the structures code, we are required to use the boundary conditions that are built into those codes. An easy way, from an implementation point of view, to use the two codes in the multidisciplinary setting if to run the two codes sequentially, exchanging information between them as needed. This approach, however, may converge slowly or not at all. The flexibility afforded by our approach means that we can choose, in setting up the subdomain problems, the boundary conditions that are already being used for the individual disciplinary problems. The optimization based strategy also allows for the individual disciplinary problems to be solved in parallel and the analytical results we have obtained result in algorithms with known convergence properties. We are currently further exploring, from both the computational and analytical points of view, the use of our optimization-based domain decomposition approach in complex multidisciplinary problems including fluid-structure interaction problems.

Optimization problems

The optimization-based domain decomposition approach has also been applied to optimization problems for partial differential equations. Here, the original problem involves the minimization of a functional with the partial differential equations problem playing the roles of constraints on the minimization problem. We subdivide the region into subdomains and pose the partial differential equation constraints in each subdomain. Again, as before, we have unknown data in the boundary conditions posed along the interfaces between subdomains. We then define a new objective functional that is a weighted sum of the original objective functional and the functional that measures the jumps in the solution across the interfaces between subdomains. Finally, we minimize the new objective functional with respect to both the control parameters of the original optimization problem and the unknown data in the subdomain problem boundary conditions. We have shown that, in appropriate limits of the weighting parameters in the new functional, that the solution of the new optimization problem converges to the solution of the original problem. We have also studied gradient methods for solving the optimization problem and demonstrated that the subdomain problems may be solved in parallel. We have also carried out some computational experiments that illustrate the implementation of our approach.

Issues in the implementation of substructuring algorithms for the Navier-Stokes equations; Advances in Computer Methods for Partial Differential Equations V, IMACS, 1984, 57-63; M. Gunzburger and R. Nicolaides.

On substructuring algorithms and solution techniques for the numerical approximation of partial differential equations; Appl. Numer. Methods 2, 1986, 243-256; M. Gunzburger and R. Nicolaides.

A domain decomposition method for the Navier-Stokes equations; Proc. 17th Workshop in Pure Mathematics Korean Academic Council, Seoul, 1998, 13-33; M. Gunzburger and H.-K. Lee.

Domain decomposition for partial differential equations through optimization; to appear in Proc. Korean Advanced Institute for Science and Technology Workshop on Finite Elements; M. Gunzburger, H.-K. Lee and Janet Peterson.

An optimization based domain decomposition method for partial differential equations; Comp. Math. Appl. 37, 1999, 77-93; M. Gunzburger, H.-K. Lee and J. Peterson.

Solution of elliptic partial differential equations by an optimization-based domain decomposition method; Appl. Math. Comput. 113, 2000, 111-139; M. Gunzburger, M. Heinkenschloss and H.-K. Lee.

An optimization-based domain decomposition method for the Navier-Stokes equations; SIAM J. Numer. Anal. 37, 2000, 1455-1480; M. Gunzburger and H.-K. Lee.

A gradient method approach to optimization-based multidisciplinary simulations and nonoverlapping domain decomposition algorithms; SIAM J. Numer. Anal. 37, 2000, 1513-1541; Q. Du and M. Gunzburger.

A domain decomposition method for optimization problems for partial differential equations; Comput. Math. Appl. 40, 2000, 177--192; M. Gunzburger and J. Lee.

Optimization-based methods for multidisciplinary simulation and optimization; in Proc. 8th Annual Conference of the CFD Society of Canada, CERCA, Montreal, 2000, 689-694; J. Lee, M. Gunzburger, and Q. Du.

Analysis and approximation of a model fluid-structure interaction problem, in preparation; Q. Du, M. Gunzburger, L. Hou, and J. Lee.

An optimization-based decoupling algorithm for a fluid/structure interaction problem, in preparation; Q. Du, M. Gunzburger, and J. Lee.

Abstracts

M. Gunzburger and R. Nicolaides

A substructuring algorithm is presented which is applicable to general discretizations of the Navier-Stokes equations. The algorithm is based on a generalization of the block Gauss elimination procedure to systems having indefinite and nonsymmetric coefficient matrices. Special attention is paid to the efficient implementation of the algorithm. In particular, it is shown that the method can be carried out through a variant of Gauss elimination.

M. Gunzburger and R. Nicolaides

Substructuring methods are in common use in structural mechanics problems where typically the associated linear systmes of algebraic equations are positive definite. Here these methods are extended to problems which lead to nonpositive definite, nonsymmetric matrices. The extension is based on an algorithm which carries out the block Gauss elimination procedure without the need for interchanges even when a pivot matrix is singular. Examples are provided wherein the method isused in connection with finite element solutions of the stationary Stokes equations and the Helmholtz equation, and dual methods for second-order elliptic equations.

M. Gunzburger and H.-K. Lee

A domain decomposition method for the solution of the Navier-Stokes equations is presented. The method is based on a constrained minimization problem for which the objective functional measures the jump in the dependent variables across the common boundaries between subdomains. The optimization problem is constrained by the Navier-Stokes equations in each subdomain along with suitably chosen boundary conditions along the interfaces. We show that solutions of the minimization problem exist and derive an optimality system from which these solutions may be determined. Finite element approximations of the solutions of the optimality system are examined. The domain decomposition method is also reformulated as a nonlinear least-squares problem.

M. Gunzburger, H.-K. Lee and Janet Peterson

A domain decomposition method for the solution of the elliptic partial differential equations is presented. The method is based on a constrained minimization problem for which the objective functional measures the jump in the dependent variables across the common boundaries between subdomains. The optimization problem is constrained by the partial differential equations in each subdomain along with suitably chosen boundary conditions along the interfaces. We show that solutions of the minimization problem exist and derive an optimality system from which these solutions may be determined. Finite element approximations of the solutions of the optimality system are examined as is a gradient method for solving the optimality system. The domain decomposition method is also reformulated as a nonlinear least-squares problem. Finally, remarks are given on the extension of the method to nonlinear problems.

M. Gunzburger, H.-K. Lee and Janet Peterson

An optimization-based domain decomposition method for the solution of partial diffeerntial equations is presented. The crux of the method is a constrained minimization problem for which the objective functional measures the jump in the dependent variables across the common boundaries between subdomains; the constraints are the partial differential equations. The existence of optimal solutions for the optimization problem is shown as is the convergence to the exact solution of the given problem. We then derive an optimality system of partial differential equations from which solutions of the domain decomposition problem may be determined. Finite element approximations to solutions of the optimality system are defined and analyzed as well as an eminently parallelizable gradient method for solving the optimality system. Then, the results of some numerical experiments and some concluding remarks are given. The latter includes the extension of the method to nonlinear problems such as the Navier-Stokes equations.

M. Gunzburger, M. Heinkenschloss and H.-K. Lee

An optimization-based, non-overlapping domain decomposition method for the solution of elliptic partial differential equations is presented. The crux of the method is a constrained minimization problem for which the objective functional measures the jump in the dependent variables across the common boundaries between subdomains; the constraints are the partial differential equations. The method is reformulated as a linear least-squares problem. The latter is examined and a conjugate gradient method for its solution is presented and analyzed. The results of some numerical experiments are also given.

M. Gunzburger and H.-K. Lee

An optimization-based, non-overlapping domain decomposition method for the solution of the Navier-Stokes equations is presented. The crux of the method is a constrained minimization problem for which the objective functional measures the jump in the dependent variables across the common boundaries between subdomains; the constraints are the Navier-Stokes equations in the subdomains with suitably chosen boundary conditions along the interfaces. We show that solutions of the minimization problem exist and derive an optimality system from which these solutions may be determined. Finite element approximations of the solutions of the optimality system are examined. The domain decomposition method is also reformulated as a nonlinear least-squares problem and the results of some numerical experiments are given.

Q. Du and M. Gunzburger

It has been shown recently that optimization based nonoverlapping domain decomposition algorithms are connected to many well-known algorithms. Using a gradient type iterative strategy for the optimization problem, we present further discussion on how to do develop various algorithms that can integrate subdomain solvers into a solver for the problem in the whole domain. In particular, the algorithms we discuss can be used to develop efficient solvers of multidisciplinary problems which are constructed using existing subdomain solvers without the need for making changes in the latter.

M. Gunzburger and J. Lee

We consider an optimization-based domain decomposition approach for optimization problems for partial differential equations. Here, the given optimization problem involves the minimization of a functional that depends on the solution of a boundary value problem for a partial differential equation. The minimization is with respect to some unknown data in the boundary value problem. We subdivide the region into subdomains and pose the partial differential equation constraints in each subdomain. The subdomain boundary value problems have boundary conditions along the interfaces between the subdomains that contain unknown data. We also define a new objective functional that is a weighted sum of the original objective functional and a functional that measures the jumps in the solution across the interfaces between subdomains. Finally, we minimize the new objective functional with respect to both the unknown parameters in the given optimization problem and the unknown data introduced in the definition of the subdomain problems. We show, in an appropriate limit for the weighting parameters in the new functional, that the solution of the new optimization problem converges to the solution of the original problem. We study a gradient method for solving the new optimization problem and demonstrate that the subdomain problems may be solved in parallel. We also provide the results of some computational experiments that illustrate the implementation of our approach.

J. Lee, M. Gunzburger, and Q. Du

We discuss algorithms for multidisciplinary simulation and optimization that efficiently couple existing single-discipline codes. The algorithms are based on a strategy in which unknown data at the interfaces is determined through an optimization process. The strategy allows for the user to select the data type at the interfaces for each discipline, so that the method can be tailored to existing codes. We focus on the fluid-structure interaction problem for which we describe the optimization-based methods.

Return to

E-mail to Max Gunzburger

Last updated: December 10, 2001 by Max Gunzburger