Parallelizing FEM for elliptical PDEs with n >1

Question

For a little personal project, I am picking up my FEM skills again. I learned a lot about the theory back in university and I am able to implement a simple FEM solver for specific problems but I was curious about the different parallelization possibilities because we never went into those too deeply.

Let us focus on the Poisson equation for simplicity in some "nice" domain for n >1. From what I have seen, one can

• Parallelize the assembly of the stiffness matrix. This takes quite some time for larger problems and can be parallelized easily.
• Parallelize the linear solver. Here there are lots of possibilities to construct specific solvers for sparse systems based on CG, multigrid or Krylov-based methods. Also possible but a little harder.
• Domain Decomposition. If I understood that topic correctly one can solve some sub-areas of the domain and divide the solution of that onto several processors.

I am not a researcher in the topic but would like to gain a deeper understanding in the topic — mainly not by using some available library (I am well aware of FEniCS et al.) but code the first simple examples for parallelization by hand. For example, I keep reading that DG FEM is supposed to scale a little bit better on a parallel level and from some slides I can guess why — you have smaller assumptions on continuity, so the faces of your elements do not need to be coupled strongly. I have however trouble finding some extensive discussion with relating examples about this.

I cannot find really well-explained material on the last topic either, I know it exists but I couldn't find comprehensive material on that topic either. Most jump from the formulation of the discretization to "… and then I used METIS plus xyz to solve. Here are three graphs showing convergence". It is of course also really tiring to try to reverse-engineer code found somewhere that "seems" to do what I think it does.

Questions

• From those who know, are there known books on that topic I could read?

• Could someone point me in the right direction?

• Or would someone with some experience in those topics give a small introduction into the topic?

Answer 1

I think you've identified some of the major issues. Yes, Finite Element methods are very parallel, because you have all these elements that can often be treated in parallel, but the devil is in the details. To address some of your points:

1. Assembly is an interesting point. For Finite Difference methods you can pretty much assemble the whole thing perfectly in parallel. With FE you get the phenomenon that two elements contribute integrals to their shared nodes/edges/faces. And what if two elements are evaluated by different processors? Then you have to resolve that simultaneous access.
2. Solvers. A simple Jacobi method, apart from its limited convergence conditions, is fully parallel. Methods such as CG converge much faster and in more cases, but they contain inner products, which are something to worry about, especially if you get in the hundreds of thousands of processors/cores. There is tons of literature about this. Usually, the first issue to worry about is the matrix-vector product. For regular grids that is easy to parallelize, for irregular grids programming becomes a headache, certainly in distributed memory.
3. Domain Decomposition. That is both a metaphorical term for "domain partitioning" and the name of a certain mathematical method that relies on the better conditioning of interface systems. Feel free to read up on trace theorems in functional analysis. So let me just address the partitioning part: yes, fruitful parallel methods are based on solving subproblems. For instsance there is Block Jacobi and the Additive Schwarz method. Both of these are typically used as preconditioners in a CG (or BiCGstab or GMRES) method.

A lot of these topics are discussed in my HPC book: http://pages.tacc.utexas.edu/~eijkhout/istc/istc.html