Government Documents

36 pages
4 views

A non-overlapping domain decomposition method with non-matching grids for modeling large finite antenna arrays

Please download to get full document.

View again

of 36
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
A non-overlapping domain decomposition method with non-matching grids for modeling large finite antenna arrays
Transcript
  A Non-overlapping Domain Decomposition Methodwith Inexact Solvers 1 Qiya Hu and Dudu Sun LSEC, Institute of Computational Mathematics and Scientific/Engineering Computing,Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Abstract In this paper we are concerned with non-overlapping domain decomposition methodsfor the second-order elliptic problems in three-dimensional domains. We develop anew kind of substructuring method, in which one can use an inexact solver both ineach subdomain and on each local interface. The main ideas are to decompose theinterface space into the sum of small local subspaces and a series of coarse subspacesspanned by  constant-like   basis functions, and to design a cheap approximate harmonicextension of the  constant-like   function. It will be shown that the condition number of the preconditioned system grows only as the logarithm of the dimension of the localproblem associated with an individual substructure, and is independent of possible jumps of the coefficient in the elliptic equation. Key words . domain decomposition, interface space, multilevel decomposition,constant-like function, nearly harmonic extension, preconditioner, inexact solvers,condition number AMS(MOS) subject classification  65F10, 65N30, 65N55 1 Introduction Non-overlapping domain decomposition methods (DDMs) have been shown to be pow-erful techniques for solving large-scale partial differential equations, especially for solvingpartial differential equations with large jump coefficients, and for solving coupled partialdifferential equations. One’s main task in non-overlapping DDMs is the construction of anefficient substructuring preconditioner for discretization system associated with the partialdifferential equations. The construction of this preconditioner has been investigated fromvarious ways and to various models in literature, see, for example, [1]-[9], [11]-[15], [17]-[21],[23]-[24], [26].Most non-overlapping DDMs studied so far require exact subdomain solvers; we refer[25] and [29] (and the references cited therein). Such a requirement severely degrade the ef-ficiency of the methods. There are only a few works studying substructuring methods withinexact subdomain solvers [3], [4] and [9]. In [3], analysis and numerical experiments withinexact algorithms of Neumann-Dirichlet type was done under the additional assumptionof high accuracy of the inexact solvers. The essential difficulty is that discrete harmonicextensions on each subdomain are used in non-overlapping domain decomposition methods.In [4], the harmonic extension on a subdomain was replaced by a simple  average   extension,and substructuring preconditioners with the average extension are constructed. Because of such  average   extension, nearly optimal convergence can not be gotten for these substruc-turing preconditioners. To avoid harmonic extensions, [9] considered so called  approximate  harmonic basis functions, which still involve high accuracy of the inexact solvers. It seemsdifficult to construct a nearly optimal substructuring preconditioner with inexact solverswithout any additional assumption. 1 The work is was supported by Natural Science Foundation of China G10771178, The Key Projectof Natural Science Foundation of China G10531080, and National Basic Research Program of ChinaG2005CB321702. (email: hqy@lsec.cc.ac.cn) 1  In the present paper, inspired by [9] and [4], we make a new attempt for the designof substructuring preconditioner with inexact solvers. The core work is the constructionof a kind of multilevel  nearly   harmonic basis on general quasi-uniform meshes. The mainingredients in our construction are: (i) develop a special multilevel space decomposition tothe interface space; (ii) design a cheap  nearly   harmonic extension for each basis function of the subspaces involved in the decomposition. It will be shown that the new substructuringpreconditioner possesses nearly optimal convergence, which is independent of possible large jumps of the coefficient across the interface. For the new method, no additional assumptionis required , and the total computational complexity is optimal.The outline of the remainder of the paper is as follows. In Section 2, we introducesome notation and our motive. In Section 3, we present a multilevel decomposition for theinterface space. The main results on the substructuring preconditioner are described inSection 4. In Section 5, we give an analysis of the convergence of the preconditioner. Insection 6, we prove the stability of the extension of   constant-like   function, which is used inSection 5. Some numerical results are reported in Section 7. 2 Preliminaries 2.1 Domain decomposition Let Ω be a bounded polyhedron in  R 3 . Consider the model problem  − div ( ω ∇ u ) =  f, in  Ω ,u  = 0 , on ∂  Ω ,  (2.1)where  ω  ∈  L ∞ (Ω) is a positive function.Let  H  10 (Ω) denote the standard Sobolev space, and let ( · , · ) denote the  L 2 (Ω)-innerproduct. The weak formulation of (2.1) in  H  10 (Ω) is then given by the following. Find   u  ∈  H  10 (Ω)  such that  A ( u,v ) = ( f,v )  ∀ v  ∈  H  10 (Ω) ,  (2.2)where ( · , · ) is the scalar product in  L 2 (Ω), and A ( u,v ) =   Ω ω ∇ u ·∇ vdp. We will apply a kind of non-overlapping domain decomposition method to solving (2.2).For simplicity of exposition, we consider only the case with matching grids in this paper.Let  T  h  =  { τ  i }  be a regular and quasi-uniform triangulation of Ω with  τ  ′ i s  being non-overlapping simplexes of size  h  ( ∈  (0 , 1]). The set of notes of   T  h  is denoted by  N  h . We thendefine  V  h (Ω) to be the piecewise linear finite element subspace of   H  10 (Ω) associated with T  h : V  h (Ω) =  { v  ∈  H  10 (Ω) :  v | τ   ∈ P  1  ∀ τ   ∈ T  h } , where  P  1  is the space of linear polynomials. Then the finite element approximation for(2.2) is to find  u h  ∈  V  h (Ω) such that A ( u h ,v h ) = ( f,v h ) ,  ∀ v h  ∈  V  h (Ω) .  (2.3)Let Ω be decomposed into the union of   n  polyhedrons Ω 1 , ··· , Ω n , which satisfy Ω i ∩ Ω  j  = ∅  when  i   =  j . We assume that each  ∂  Ω k  can be written as a union of boundaries of elements in  T  h , and all Ω k  are of size  H   in the usual sense (see [5] and [29]). Without loss of 2  generality, we assume that the coefficient  ω (  p ) is piecewise constant, then each subdomainΩ k  is chosen such that  ω (  p ) equals to a constant  ω k  in Ω k . Note that  { Ω k }  may notconstitute a triangulation of Ω.The common part of two neighboring subdomains Ω i  and Ω  j  may be a vertex, an edgeor a face. In particular, we denote by Γ ij  the common face of two neighboring subdomainsΩ i  and Ω  j  (i.e., Γ ij  =  ∂  Ω i ∩ ∂  Ω  j ). The union of all Γ ij  is denoted by Γ, which is called theinterface. In this paper, we choose Dirichlet data as the interface unknown.Define the operator  A h  :  V  h (Ω)  →  V  h (Ω) by( A h v, w ) =  A ( v,w ) = N   k =1 ω k   Ω k ∇ v ·∇ wdx, v  ∈  V  h (Ω) ,  ∀ w  ∈  V  h (Ω) . The equation (2.3) can be written as A h u h  =  f  h , u h  ∈  V  h (Ω) .  (2.4)The goal of this paper is to construct a substructuring preconditioner for  A h  based on thedomain decomposition described above. 2.2 Notations To introduce the new method, we need some more notations. Throughout this paper, asubset  G  of Ω are always understood as an open set. The closure of   G  is denoted by ¯ G . •  subdomain spacesFor subdomain Ω k , define V  h (Ω k ) =  { v | Ω k  :  ∀ v  ∈  V  h (Ω) } , and V   ph  (Ω k ) =  { v h  ∈  V  h (Ω) :  supp v h  ⊂  Ω k } . SetΩ ij  = Ω i  ∪ Γ ij  ∪ Ω  j , and define V   ph  (Ω ij ) =  { v h  ∈  V  h (Ω) :  supp v h  ⊂  Ω ij } . •  interface space and face spacesAs usual, we define the (global) interface space by W  h (Γ) =  { v | Γ  :  ∀ v  ∈  V  h (Ω) } . For each  ∂  Ω k , set W  h ( ∂  Ω k ) =  { v | ∂  Ω k  :  ∀ v  ∈  W  h (Γ) } . For a subset  G  of Γ, define˜ W  h ( G ) =  { φ h  ∈  W  h (Γ) :  supp φ h  ⊂  G } . In particular, for  G  = Γ ij , the face space ˜ W  h (Γ ij ) will be used repeatedly. •  interpolation-type operator and  constant-like   basisFor a subset  G  of Γ, define the interpolation-type operator  I  0 G  :  W  h (Γ)  →  W  h (Γ) as( I  0 G φ h )(  p ) =  φ h (  p ) ,  if   p  ∈ N  h  ∩ G, 0 ,  if   p  ∈ N  h  ∩ (Γ \ G ) . 3  In particular, we have( I  0 G 1)(  p ) =  1 ,  if   p  ∈ N  h  ∩ G, 0 ,  if   p  ∈ N  h  ∩ (Γ \ G ) . If   G  is just the union of some elements on Γ, we call  φ G  =  I  0 G 1 to be  constant-like   basisfunction on  G , which will be used repeatedly. •  integration average and algebraic averageFor a function  ϕ h  ∈  W  h (Γ), let  γ  G ( ϕ h ) denote the integration average of   ϕ h  on  G , andlet  γ  h,G ( ϕ ) denote the algebraic average of the values of   ϕ  on the nodes in  G . •  sets of faces, edges, vertices and subdomainsFor convergence, let  F  Γ  denote the set of all the faces Γ ij . Besides, let  E  Γ  and  V  Γ  denotethe set of the interior edges and the set of interior vertices generated by the decomposition¯Ω =  ¯Ω k , respectively. For an edge  e  ∈ E  Γ , let  Q e  denote the set of the indices  k  of the subdomainsΩ k  which contain  e  as an edge. Namely, Q e  =  { k  :  e  ⊂  ∂  Ω k } . DefineΩ e  =  k ∈Q e Ω k ,  e  ∈ E  Γ . •  face inner-products, scaling norm and interface normFor a subset  G  of Γ, let  · , · G  denote the  L 2 inner product on  G . In particular, the · , · Γ  is abbreviated as  · , · . Let  · 0 , G  denote the norm induced from  · ,  · G .For a sub-faces  G  of Γ, let  H  G  denote the “size” of   G . Define the scaling norm  φ  12 , G  = ( | φ | 2 12 , G  + H  − 1 G   φ  20 , G ) 12 ,  ∀ φ  ∈  H  12 ( G ) . For convenience, define  φ h  ∗ , Γ  = ( n  k =1 ω k | φ h | 2 12 ,∂  Ω k ) 12 ,  ∀ φ h  ∈  W  h (Γ) . •  discrete norms and discrete inner-productDiscrete norms (or semi-norms) of finite element functions will be used repeatedly inthis paper, since the discrete norms are defined on a set of nodes only, and do not dependon the geometric shape of the underlying domain.We first give definitions of three well known discrete norms (refer to [29]), which areequivalent to their respective continuous norms. For  v h  ∈  V  h (Ω k ), the discrete  H  1 semi-norm is defined by | v h | 21 , h,  Ω k  =  h 3    p i , p j ∈N  h ∩ Ω k | v h (  p i ) − v h (  p  j ) | 2 , where  p i  and  p  j  denote two neighboring nodes. Similarly, the discrete  L 2 norm on an edge e  of Ω k  is defined by  v h  20 , h,  e  =  h   p ∈N  h ∩ e | v h (  p ) | 2 . Let  G  ⊂  Γ ij  be the union of some elements. Define the discrete  H  12  semi-norm on  W  h ( G )by | ϕ h | 2 h,  12 , G  =   p ∈N  h ∩ G  q ∈N  h ∩ G | ϕ h (  p ) − ϕ h ( q  ) | 2 |  p − q  | 3  , ϕ h  ∈  W  h ( G ) , 4  where  p  and  q   denote two different nodes on  G .Then, we define a discrete inner-product. For each  ∂  Ω k , set  φ,ψ  h, ∂  Ω k  =   p ∈N  h ∩ ∂  Ω k  q ∈N  h ∩ ∂  Ω k ( φ (  p ) − φ ( q  ))( ψ (  p ) − ψ ( q  )) |  p − q  | 3  , φ, ψ  ∈  W  h ( ∂  Ω k ) , where  p  and  q   denote two different nodes on  ∂  Ω k . Define discrete  H  12  inner-product on W  h (Γ) by  φ,ψ  h, Γ  = n  k =1 ω k  φ,ψ  h,∂  Ω k , φ, ψ  ∈  W  h (Γ) . •  H  12 00  normsLet  G  ⊂  Γ ij  be the union of some elements. For a function  ϕ h  satisfying  supp ϕ h  ⊂  G ,define | ϕ h | 2 H  1200 ( G ) =  | ϕ h | 2 12 , G  +   G | ϕ h ( x ) | 2 dist ( x, ∂G ) ds ( x ) . It is known that | ϕ h | 2 H  1200 ( G ) = ∼ | ˜ ϕ h | 2 12 ,  Ω i = ∼ | ˜ ϕ h | 2 12 ,  Ω j , where ˜ ϕ h  ∈  W  h (Γ) denotes the zero extension of   ϕ h . Moreover, we have | ϕ h | 2 H  1200 ( G ) = ∼   G | ϕ h ( x ) | 2 dis ( x, ∂G ) ds ( x ) . The corresponding discrete semi-norm is defined by | ϕ h | 2 h, H  1200 ( G ) =   p ∈N  h ∩ G | ϕ h (  p ) | 2 dis (  p, ∂G ) . •  spectrally equivalencesFor simplicity, we will frequently use the notations  < ∼  and = ∼ . For any two non-negativequantities  x  and  y, x < ∼  y  means that  x  ≤  Cy  for some constant  C   independent of meshsize  h , subdomain size  d  and the related parameters.  x  = ∼  y  means  x < ∼  y  and  y < ∼  x . 2.3 Motivation We first recall the main ideas of the existing substucturing preconditions.Let  E  k  :  W  h ( ∂  Ω k )  →  V  h (Ω k ) be the discrete harmonic extension. Define the  harmonic  subspace V  Γ h  (Ω) =  { v h  ∈  V  h (Ω) :  v h | Ω k  =  E  k ( φ h | ∂  Ω k ) ( k  = 1 , ··· , n ) for some  φ h  ∈  V  h (Γ) } . Then, we have the initial space decomposition V  h (Ω) = n  k =1 V   ph  (Ω k ) + V  Γ h  (Ω) . Let  A h,k  :  V   ph  (Ω k )  →  V   ph  (Ω k ) be the restriction of the operator  A h  on the local space V   ph  (Ω k ), and let  B h, Γ  :  V  Γ h  (Ω)  →  V  Γ h  (Ω) be a symmetric and positive definite operator whichis spectrally equivalent to the restriction of the operator  A h  on the harmonic subspace5
Related Documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x