1
$\begingroup$

Question

In general, do domain decomposition methods (DDMs) require a linear system of equations $Au = f$ to be formed by finite element discretization/method (FEM) of a PDE? Or could one simply use a finite difference discretization/method (FDM) to form the system (e.g., see this ipynb from MIT 18.303 for a discretization of Poisson's equation) or even finite volume discretization?

Placeholder "Answer"

I have found a resource [4] that explicitly states that one could apply DDMs to a linear system from FDM since "finite differences is actually a special case of finite elements, and all the ideas in domain decomposition work in the most general context of finite elements." A relevant discussion can also be found here regarding the claim of FDM as a special case of FEM.

Context

Many texts [1-3] on domain decomposition define their algorithms (Alternating Schwarz Method, FETI, FETI-DP, BDDC, etc.) by considering the discretization of partial differential equations (PDEs) in a finite element setting (e.g., something like "consider a finite element discretization of a general 2nd order elliptic equation with dirichlet boundary conditions" from ch. 1 of ref [2]). I'm interested in using a finite difference discretization because for prototyping domain decomposition methods for second order linear elliptical PDEs (e.g., Poisson equation as a good benchmark), it would be far simpler to use a finite difference discretization to form the the system $Au = f$ than having to use a finite element library (e.g., Ferrite.jl, deal.ii) and then using the associated API to extract relevant information about degrees of freedom, connectivity, etc. I am also primarily interested in static problems, in case that is relevant.

My intuition is that one could just use a finite difference discretization, but since all the texts that I have found always consider finite element discretizations (though this may simply be due to the advantages of FEM in general), I am hesitant to make this assumption. Though, I have found an example BDDC implementation that does use a finite difference discretization.

Per @whpowell96 comment that for FEM one has the mesh information up front, I can see how one might just use FEM even for prototyping DDMs. One could feasibly use GMSH to create a simple mesh, create disjoint subdomains using either an element-oriented or vertex-oriented approach (see chapter 4.2 in [3]) and an appropriate graph partitioning scheme (e.g., METIS), and then assembling subdomain systems using FEM. With these parts assembled, my understanding is that the DDMs themselves differ in how they resolve different solutions at the interface between subdomains, so this then becomes the focus of the implementation.

References

[1] : Dolean2015: "An Introduction to Domain Decomposition: Algorithms, Theory and Parallel Implementation"

[2] : Bruaset2006: "Numerical Solution of Partial Differential Equations on Parallel Computers"

[3] : Matthew2008: "Domain Decomposition for the Numerical Solution of Partial Differential Equations"

[4] : Lecture 8: "Domain Decomposition" from MIT 18.337. url: http://courses.csail.mit.edu/18.337/2005/book/Lecture_08-Domain_Decomposition.pdf

$\endgroup$
7
  • $\begingroup$ I think "domain decomposition methods" include such a wide variety of techniques so that it is almost impossible to say in general. $\endgroup$
    – knl
    Commented Apr 26 at 12:22
  • $\begingroup$ @knl you make a very reasonable point. Perhaps there are DD methods that rely on particular aspects of FEM theory to result in favorable properties for the DD method itself as a preconditioner/solver. I suppose when I said domain decomposition method, I was thinking the major ones listed in the refs (Alternating Schwarz, FETI, FETI-DP, BDD, BDDC, and Neumann-Neumann), but it is of course a broad category. $\endgroup$ Commented Apr 26 at 12:45
  • $\begingroup$ I don't see a reason one couldn't use DD for FDM but one must be careful about setting up the boundary conditions of the subdomains. One of the reasons FEM is the primary focus is that those tend to be the largest problems and splitting the domain is easier because you already have all the mesh connectivity information up front. $\endgroup$
    – whpowell96
    Commented Apr 26 at 14:56
  • 2
    $\begingroup$ For the first one that's very common in all discretization methods, for the latter I know of additive Schwarz methods being applied to reduce ghost sync frequency in wide stencil methods, as well as the practice of sub-cycling in AMR codes (not sure if this is what you're looking for). $\endgroup$ Commented Apr 26 at 15:58
  • 1
    $\begingroup$ Overlapping DD methods can be define purely in terms of the algebraic structure of the linear system. $\endgroup$ Commented Apr 26 at 23:18

1 Answer 1

0
$\begingroup$

Domain decomposition doesn't require it to be $Au = f$, but it makes it much easier for you to find the subset from the vector $u$ that you're interested in, since your discretized forward model is just a matrix $A \in \mathbb{R}^{m \times n}$ and vector $u \in \mathbb{R}^n$, it is just a matter of applying the Schur Complement.

To elaborate, you're representing $u$ in the discretized form $u = \sum_{i=1}^n u_i \phi_i$, where each $\phi_i$ is a basis function. If you have the discretized forward model to be in the form $Au=f$, then, the subdomain of your interest is a matter of finding the subvector in $u \in \mathbb{R}^n$ that is of interest to you. So given that you can have the discretized forward model $Au=f$ to be linear, then, you just need to employ the Schur complement to take out the subvector of interest.

Your post doesn't explain your situation and merely is asking a question, so I don't know what's your purpose of using DD.

$\endgroup$
5
  • $\begingroup$ I know DD doesn't strictly require a linear system of equations (i.e., algebraic level representation), but in practice I'm not really interested in the continuous level representation of DD since that's not what gets implemented. So practically, I think what you're saying is to construct the Schur complement $S_i = A_{i}^{\Gamma\Gamma} - A_{i}^{\Gamma I} ( A_{i}^{I I} )^{-1} A_{i}^{I \Gamma}$ for a domain $\Omega$ divided into $N$ (non)overlapping subdomains $\Omega_{i}$ for $i = 1,\ ...,\ N$ you need some specification (e.g., indices) of interior $I$ and interface $\Gamma$ dofs.... $\endgroup$ Commented May 26 at 7:05
  • $\begingroup$ then once you have $S_i$, you can take out the "subvector of interest", which would be $u^{\Gamma}$ from $Su^{\Gamma} = g$ (see Sistek 2023 for details). $\endgroup$ Commented May 26 at 7:06
  • $\begingroup$ Regarding my purpose for the question, beyond pure curiosity, I state it under the # Context section with "I'm interested in using a finite difference discretization because [it's easier] for prototyping domain decomposition methods". $\endgroup$ Commented May 26 at 7:08
  • $\begingroup$ DD is separate from the numerical discretization method that you use. $\endgroup$ Commented May 26 at 7:19
  • $\begingroup$ You can use whatever numerical discretization method you want, for your domain decomposition task. Use a meshless discretization method, as an example. $\endgroup$ Commented May 26 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.