共查询到20条相似文献,搜索用时 46 毫秒
1.
James H. Bramble Joseph E. Pasciak Apostol T. Vassilev. 《Mathematics of Computation》1998,67(221):1-19
In this paper we construct and analyze new non-overlapping domain decomposition preconditioners for the solution of second-order elliptic and parabolic boundary value problems. The preconditioners are developed using uniform preconditioners on the subdomains instead of exact solves. They exhibit the same asymptotic condition number growth as the corresponding preconditioners with exact subdomain solves and are much more efficient computationally. Moreover, this asymptotic condition number growth is bounded independently of jumps in the operator coefficients across subdomain boundaries. We also show that our preconditioners fit into the additive Schwarz framework with appropriately chosen subspace decompositions. Condition numbers associated with the new algorithms are computed numerically in several cases and compared with those of the corresponding algorithms in which exact subdomain solves are used.
2.
A Dual-Primal FETI method for incompressible Stokes equations 总被引:1,自引:0,他引:1
Jing Li 《Numerische Mathematik》2005,102(2):257-275
In this paper, a dual-primal FETI method is developed for incompressible Stokes equations approximated by mixed finite elements
with discontinuous pressures. The domain of the problem is decomposed into nonoverlapping subdomains, and the continuity of
the velocity across the subdomain interface is enforced by introducing Lagrange multipliers. By a Schur complement procedure,
the solution of an indefinite Stokes problem is reduced to solving a symmetric positive definite problem for the dual variables,
i.e., the Lagrange multipliers. This dual problem is solved by the conjugate gradient method with a Dirichlet preconditioner.
In each iteration step, both subdomain problems and a coarse level problem are solved by a direct method. It is proved that
the condition number of this preconditioned dual problem is independent of the number of subdomains and bounded from above
by the square of the product of the inverse of the inf-sup constant of the discrete problem and the logarithm of the number
of unknowns in the individual subdomains. Numerical experiments demonstrate the scalability of this new method.
This work is based on a doctoral dissertation completed at Courant Institute of Mathematical Sciences, New York University.
This work was supported in part by the National Science Foundation under Grants NSF-CCR-9732208, and in part by the U.S. Department
of Energy under contract DE-FG02-92ER25127. 相似文献
3.
In this paper, a positive definite Balancing Neumann–Neumann (BNN) solver for the linear elasticity system is constructed and analyzed. The solver implicitly eliminates the interior degrees of freedom in each subdomain and solves iteratively the resulting Schur complement, involving only interface displacements, using a BNN preconditioner based on the solution of a coarse elasticity problem and local elasticity problems with natural and essential boundary conditions. While the Schur complement becomes increasingly ill-conditioned as the materials becomes almost incompressible, the BNN preconditioned operator remains well conditioned. The main theoretical result of the paper shows that the proposed BNN method is scalable and quasi-optimal in the constant coefficient case. This bound holds for material parameters arbitrarily close to the incompressible limit. While this result is due to an underlying mixed formulation of the problem, both the interface problem and the preconditioner are positive definite. Numerical results in two and three dimensions confirm these good convergence properties and the robustness of the methods with respect to the almost incompressibility of the material. 相似文献
4.
Summary. The boundary element method (BEM) is of advantage in many applications including far-field computations in magnetostatics
and solid mechanics as well as accurate computations of singularities. Since the numerical approximation is essentially reduced
to the boundary of the domain under consideration, the mesh generation and handling is simpler than, for example, in a finite
element discretization of the domain. In this paper, we discuss fast solution techniques for the linear systems of equations
obtained by the BEM (BE-equations) utilizing the non-overlapping domain decomposition (DD). We study parallel algorithms for
solving large scale Galerkin BE–equations approximating linear potential problems in plane, bounded domains with piecewise
homogeneous material properties. We give an elementary spectral equivalence analysis of the BEM Schur complement that provides
the tool for constructing and analysing appropriate preconditioners. Finally, we present numerical results obtained on a massively
parallel machine using up to 128 processors, and we sketch further applications to elasticity problems and to the coupling
of the finite element method (FEM) with the boundary element method. As shown theoretically and confirmed by the numerical
experiments, the methods are of algebraic complexity and of high parallel efficiency, where denotes the usual discretization parameter.
Received August 28, 1996 / Revised version received March 10, 1997 相似文献
5.
Summary. In this paper we develop an efficient Schur complement method for solving the 2D Stokes equation. As a basic algorithm, we
apply a decomposition approach with respect to the trace of the pressure. The alternative stream function-vorticity reduction
is also discussed. The original problem is reduced to solving the equivalent boundary (interface) equation with symmetric
and positive definite operator in the appropriate trace space. We apply a mixed finite element approximation to the interface
operator by
iso
triangular elements and prove the optimal error estimates in the presence of stabilizing bubble functions. The norm equivalences
for the corresponding discrete operators are established. Then we propose an asymptotically optimal compression technique
for the related stiffness matrix (in the absence of bubble functions) providing a sparse factorized approximation to the Schur
complement. In this case, the algorithm is shown to have an optimal complexity of the order , q = 2 or q = 3, depending on the geometry, where N is the number of degrees of freedom on the interface. In the presence of bubble functions, our method has the complexity
arithmetical operations. The Schur complement interface equation is resolved by the PCG iterations with an optimal preconditioner.
Received March 20, 1996 / Revised version received October 28, 1997 相似文献
6.
Summary. Multilevel preconditioners are proposed for the iterative solution of the discrete problems which arise when orthogonal spline
collocation with piecewise Hermite bicubics is applied to the Dirichlet boundary value problem for a self-adjoint elliptic
partial differential equation on a rectangle. Additive and multiplicative preconditioners are defined respectively as sums
and products of independent operators on a sequence of nested subspaces of the fine partition approximation space. A general
theory of additive and multiplicative Schwarz methods is used to prove that the preconditioners are spectrally equivalent
to the collocation discretization of the Laplacian with the spectral constants independent of the fine partition stepsize
and the number of levels. The preconditioned conjugate gradient and preconditioned Orthomin methods are considered for the
solution of collocation problems. An implementation of the methods is discussed and the results of numerical experiments are
presented.
Received March 1, 1994 / Revised version received January 23, 1996 相似文献
7.
Balancing Neumann‐Neumann methods are introduced and studied for incompressible Stokes equations discretized with mixed finite or spectral elements with discontinuous pressures. After decomposing the original domain of the problem into nonoverlapping subdomains, the interior unknowns, which are the interior velocity component and all except the constant‐pressure component, of each subdomain problem are implicitly eliminated. The resulting saddle point Schur complement is solved with a Krylov space method with a balancing Neumann‐Neumann preconditioner based on the solution of a coarse Stokes problem with a few degrees of freedom per subdomain and on the solution of local Stokes problems with natural and essential boundary conditions on the subdomains. This preconditioner is of hybrid form in which the coarse problem is treated multiplicatively while the local problems are treated additively. The condition number of the preconditioned operator is independent of the number of subdomains and is bounded from above by the product of the square of the logarithm of the local number of unknowns in each subdomain and a factor that depends on the inverse of the inf‐sup constants of the discrete problem and of the coarse subproblem. Numerical results show that the method is quite fast; they are also fully consistent with the theory. © 2002 John Wiley & Sons, Inc. 相似文献
8.
In this paper, we consider a non-overlapping domain decomposition method combined with the characteristic method for solving optimal control problems governed by linear convection–diffusion equations. The whole domain is divided into non-overlapping subdomains, and the global optimal control problem is decomposed into the local problems in these subdomains. The integral mean method is utilized for the diffusion term to present an explicit flux calculation on the inter-domain boundary in order to communicate the local problems on the interfaces between subdomains. The convection term is discretized along the characteristic direction. We establish the fully parallel and discrete schemes for solving these local problems. A priori error estimates in \(L^2\)-norm are derived for the state, co-state and control variables. Finally, we present numerical experiments to show the validity of the schemes and verify the derived theoretical results. 相似文献
9.
We study two-level additive Schwarz preconditioners that can be used in the iterative solution of the discrete problems resulting
from C0 interior penalty methods for fourth order elliptic boundary value problems. We show that the condition number of the preconditioned
system is bounded by C(1+(H3/δ3)), where H is the typical diameter of a subdomain, δ measures the overlap among the subdomains and the positive constant C is independent of the mesh sizes and the number of subdomains.
This work was supported in part by the National Science Foundation under Grant No. DMS-03-11790. 相似文献
10.
For any continuous bilinear form defined on a pair of Hilbert spaces satisfying the compatibility Ladyshenskaya–Babušca–Brezzi condition, symmetric Schur complement operators can be defined on each of the two Hilbert spaces. In this paper, we find bounds for the spectrum of the Schur operators only in terms of the compatibility and continuity constants. In light of the new spectral results for the Schur complements, we review the classical Babušca–Brezzi theory, find sharp stability estimates, and improve a convergence result for the inexact Uzawa algorithm. We prove that for any symmetric saddle point problem, the inexact Uzawa algorithm converges, provided that the inexact process for inverting the residual at each step has the relative error smaller than 1/3. As a consequence, we provide a new type of algorithm for discretizing saddle point problems, which combines the inexact Uzawa iterations with standard a posteriori error analysis and does not require the discrete stability conditions. 相似文献
11.
12.
If the stationary Navier–Stokes system or an implicit time discretization of the evolutionary Navier–Stokes system is linearized by a Picard iteration and discretized in space by a mixed finite element method, there arises a saddle point system which may be solved by a Krylov subspace method or an Uzawa type approach. For each of these resolution methods, it is necessary to precondition the Schur complement associated to the saddle point problem in question. In the work at hand, we give upper and lower bounds of the eigenvalues of this Schur complement under the assumption that it is preconditioned by a pressure convection–diffusion matrix. 相似文献
13.
Summary. In the Dual-Primal FETI method, introduced by Farhat et al. [5], the domain is decomposed into non-overlapping subdomains,
but the degrees of freedom on crosspoints remain common to all subdomains adjacent to the crosspoint. The continuity of the
remaining degrees of freedom on subdomain interfaces is enforced by Lagrange multipliers and all degrees of freedom are eliminated.
The resulting dual problem is solved by preconditioned conjugate gradients. We give an algebraic bound on the condition number,
assuming only a single inequality in discrete norms, and use the algebraic bound to show that the condition number is bounded
by for both second and fourth order elliptic selfadjoint problems discretized by conforming finite elements, as well as for
a wide class of finite elements for the Reissner-Mindlin plate model.
Received January 20, 2000 / Revised version received April 25, 2000 / Published online December 19, 2000 相似文献
14.
C. Palencia 《Numerische Mathematik》1999,82(3):471-490
We consider semidiscretizations in time, based on the backward Euler method, of an abstract, non-autonomous parabolic initial
value problem where , , is a family of sectorial operators in a Banach space X. The domains are allowed to depend on t. Our hypotheses are fulfilled for classical parabolic problems in the , , norms. We prove that the semidiscretization is stable in a suitable sense. We get optimal estimates for the error even when
non-homogeneous boundary values are considered. In particular, the results are applicable to the analysis of the semidiscretizations
of time-dependent parabolic problems under non-homogeneous Neumann boundary conditions.
Received October 17, 1997 / Revised version received April 17, 1998 相似文献
15.
We propose a splitting method for solving equilibrium problems involving the sum of two bifunctions satisfying standard conditions. We prove that this problem is equivalent to find a zero of the sum of two appropriate maximally monotone operators under a suitable qualification condition. Our algorithm is a consequence of the Douglas–Rachford splitting applied to this auxiliary monotone inclusion. Connections between monotone inclusions and equilibrium problems are studied. 相似文献
16.
S. H. Lui 《Numerische Mathematik》2002,93(1):109-129
Summary The Schwarz Alternating Method can be used to solve elliptic boundary value problems on domains which consist of two or more
overlapping subdomains. The solution is approximated by an infinite sequence of functions which results from solving a sequence
of elliptic boundary value problems in each subdomain.
In this paper, proofs of convergence of some Schwarz Alternating Methods for nonlinear elliptic problems which are known to
have solutions by the monotone method (also known as the method of subsolutions and supersolutions) are given. In particular,
an additive Schwarz method for scalar as well some coupled nonlinear PDEs are shown to converge to some solution on finitely
many subdomains, even when multiple solutions are possible. In the coupled system case, each subdomain PDE is linear, decoupled
and can be solved concurrently with other subdomain PDEs. These results are applicable to several models in population biology.
This work was in part supported by a grant from the RGC of HKSAR, China (HKUST6171/99P) 相似文献
17.
Nonsymmetric saddle point problems arise in a wide variety of applications in computational science and engineering. The aim of this paper is to discuss the numerical behavior of several nonsymmetric iterative methods applied for solving the saddle point systems via the Schur complement reduction or the null-space projection approach. Krylov subspace methods often produce the iterates which fluctuate rather strongly. Here we address the question whether large intermediate approximate solutions reduce the final accuracy of these two-level (inner–outer) iteration algorithms. We extend our previous analysis obtained for symmetric saddle point problems and distinguish between three mathematically equivalent back-substitution schemes which lead to a different numerical behavior when applied in finite precision arithmetic. Theoretical results are then illustrated on a simple model example. 相似文献
18.
Susanne C. Brenner 《Numerische Mathematik》1999,83(2):187-203
Summary. It is shown that for elliptic boundary value problems of order 2m the condition number of the Schur complement matrix that appears in nonoverlapping domain decomposition methods is of order
, where d measures the diameters of the subdomains and h is the mesh size of the triangulation. The result holds for both conforming and nonconforming finite elements.
Received: January 15, 1998 相似文献
19.
We present an iterative domain decomposition method for the optimal control of systems governed by linear partial differential equations. The equations can be of elliptic, parabolic, or hyperbolic type. The space region supporting the partial differential equations is decomposed and the original global optimal control problem is reduced to a sequence of similar local optimal control problems set on the subdomains. The local problems communicate through transmission conditions, which take the form of carefully chosen boundary conditions on the interfaces between the subdomains. This domain decomposition method can be combined with any suitable numerical procedure to solve the local optimal control problems. We remark that it offers a good potential for using feedback laws (synthesis) in the case of time-dependent partial differential equations. A test problem for the wave equation is solved using this combination of synthesis and domain decomposition methods. Numerical results are presented and discussed. Details on discretization and implementation can be found in Ref. 1. 相似文献
20.
Summary.
We analyze the convergence of a substructuring iterative method
with Lagrange multipliers, proposed recently by Farhat and Roux.
The method decomposes finite element
discretization of an elliptic boundary value problem into
Neumann problems on the subdomains plus a coarse problem for the
subdomain nullspace components. For linear conforming elements and
preconditioning by the Dirichlet problems on the subdomains,
we prove the asymptotic bound on the condition number
,
or ,where
is the characteristic element size and
subdomain size.
Received January 3, 1995 相似文献