5
$\begingroup$

I have heard of space-time finite element methods. Although I was able to find some articles that describe the different possible methods from a mathematical point of view (thanks to Space-time finite element discretization for time-dependent PDEs for instance), I would like to know with more detail what are the main advantages (and disadvantages also) of such methods.

  • For instance, what are the improvements obtained when used in an elastodynamics problem, a fluid dynamics problem, or in a fluid-structure interaction problem over a traditional method of lines?

  • What can be achieved that could not be achieved before?

$\endgroup$
  • 1
    $\begingroup$ The main disadvantage is cost. Imagine all degrees of freedom from all elements in the spatial domain coupled together between all timesteps. That’s a huge system of equations to solve! $\endgroup$ – Paul Apr 7 at 14:55
  • 1
    $\begingroup$ @Paul: It is actually way better than you suspect. I will write about why that is so shortly. $\endgroup$ – spektr Apr 7 at 15:05
  • $\begingroup$ @spektr: Excellent! I’m glad to learn of faster methods! $\endgroup$ – Paul Apr 7 at 15:07
  • 1
    $\begingroup$ I'd like to mention the following advantages: space-time methods allow more resources for adaptive mesh refinement and numerical upscaling, and allow to use more parallelism (when the parallelization in space gets saturated). The cost is of course the main disadvantage. Another one is that meshing gets much more complicated in 4d and higher. $\endgroup$ – VorKir Apr 7 at 19:35
  • $\begingroup$ doesn't the system matrix possess some kind of Kronecker product structure that can be exploited? $\endgroup$ – sssssssssssss Apr 7 at 21:04
4
$\begingroup$

I am uniquely qualified to talk about this approach as I am a current student of Jeff Erickson (advisor to Shripad Thite mentioned in that first link) and Robert Haber doing research on the spacetime meshing side of this Spacetime Discontinuous Galerkin approach.

Fundamentally, this Spacetime Discontinuous Galerkin approach is quite different relative to more common method of lines approaches. There's many advantages to this approach that make it very exciting relative to more traditional approaches, though it ultimately has the disadvantage of being way more complex to build.


Typical Approaches

Typical marching schemes of all varieties have the benefit of being quite simple when you approach stepping through time, though obviously spatial aspects of solving the PDEs can have a range of complexity depending on your solution technique (Finite Differences, Finite Volume, Finite Element, etc.) and whether your mesh is structured, unstructured, adaptive, and/or moving.

A key drawback with time marching like this is that in between two time-slices of your PDE solution, you don't really know what the best interpolation scheme is to use between the solutions at $t_k$ and $t_k + \Delta t$. One might lazily choose linear interpolation because they assume $\Delta t$ is small enough that such an approximation is good enough. Some might use more complicated post processing techniques by considering more information than what is found in just two time-slices of your solution. Either way, you are ultimately guessing what is an adequate interpolation scheme. Obviously this could be problematic if your $\Delta t$ isn't actually small enough and/or if your PDE is nonlinear.

Traditional marching schemes do have a fairly simple approach to parallelizing the solution procedure though, namely by decomposing the mesh into disjoint chunks and using separate processes to process chunks of the PDE solution local to its mesh chunk, only communicating with other meshes to handle shared boundaries between different disjoint mesh chunks. Obviously distributed parallel solution procedures also exist for solving large sparse matrices that might be formed for large implicit time stepping problems, so there's infrastructure there as well people can leverage. Of course, there's a lot of synchronization overhead since a given process must wait for a given time step to complete across (essentially) the whole mesh.


Spacetime Discontinuous Galerkin Approach

Compared to the above techniques, this technique is actually quite a different beast. This technique is, first and foremost, an implicit method that has the usual benefits in terms of stability. In the most naive approach, it also has the typical downfall of a implicit method, in that it is computationally demanding per timestep. In this naive approach, one can essentially "time march" by taking the mesh $\Omega$ (assume represented as a simplicial mesh) and extruding it into a spacetime slab by doing $\Omega \times [t_k, t_k + \Delta t]$, ultimately being made up of spacetime simplicial prisms. Each prism $\omega_i \times [t_k, t_k + \Delta t] \subset \Omega \times [t_k, t_k + \Delta t]$ would be coupled to a constant number of simplicial prisms in the previous spacetime slab $\Omega \times [t_k - \Delta t, t_k]$. Within each simplicial prism, you will have some local spacetime basis defined, meaning each simplicial prism will have some number of degrees of freedom it contributes to what will ultimately be a pretty big matrix solve for each spacetime slab. The benefit of this over typical time marching, though, is you now know how to compute your solution at any time! No need to guess how to interpolate between two time slices.. you have all the data you need to compute a time-slice yourself anywhere!

Now of course, one might consider it not worthwhile to go through the complication of forming spacetime simplicial prisms and dealing with solving the large sparse system of equations that could come out of each spacetime slab solution. That is fair and as @Paul mentioned in the comments, that would be costly! But..

There is actually a way more interesting way to do things!

Fundamentally, we turn our attention to properties of systems of Hyperbolic PDEs. We know that the nature of the characteristics of such systems is such that a given location in spacetime depends on a cone of information that comes before it in time, something along the lines of the image below

enter image description here

We can use this information to do something much smarter. For simplicity, let us assume the characteristic wavespeeds are constant throughout spacetime. Let us also just consider solving a problem in 1D x Time to make things simple. Under these assumptions, let the initial spacetime mesh will simply be the initial space mesh, a 1D line, as shown below at $t = 0$. Notice that I show the characteristics at the top right, $w_1$ and $w_2$, and I define $u_2$ to be a more limiting characteristic than $w_2$ since $u_2$ has the faster wavespeed of $w_1$ (since $\left\lVert\frac{dt}{dx}\right\rVert$ for $w_1$ is smaller than for $w_2$).

enter image description here

From here, what might we be able to do? Well, consider the pitch of one of the vertices shown below. As is shown in the diagram, this pitch generated a set of spacetime simplices such that any point inside this patch of spacetime triangles is only dependent in known information (the initial condition at the bottom facets, in this case). When a spacetime simplex has this property, it is named as being causal. A patch comprised of simplices that are causal is also a causal patch. Indeed, by forming causal patches around a vertex, this propery actually allows you to solve this spacetime patch independently of the rest of the spacetime mesh (which we have yet to explicitly construct)! This actually induces an algorithm that only requires you to solve systems of equations for patches, which are constant sized relative to the size of the input spatial mesh!

enter image description here

But there's more! Consider the sample spacetime mesh that has been constructed and solved so far shown below. Gray and green triangles are causal spacetime simplices that have already been solved for their degrees of freedom and the purple triangles are a recently pitched patch that is about to be solved, which we will term as active spacetime simplices.

enter image description here

First notice that this causal pitching behavior allows different parts of the domain to capture much more of spacetime in one patch than other parts. This is important! This technique automatically adapts the "time step" based on the geometric and causal properties of the hyperbolic system without requiring all of the mesh to be penalized for, say, having a really tiny simplex in some part of the mesh. This means you can make tons of progress in your solution really fast in coarser parts of your mesh!

Notice as well that the only simplices that have information flowing into the active simplices are the ones marked in green. This structure is consistent throughout this meshing approach and allows us to not require storing the whole spacetime mesh at any given moment that we produce, but only requires storing spacetime cells that have facets that will be incident on future active simplices. This means we can propagate through spacetime with a mesh proportional to size as the input spatial mesh we started with and that's it!

So if you consider this algorithmically, for an initial mesh that is $O(n)$ in size, where $n$ is the number of spatial simplices, each tent-pitch requires $O(1)$ simplices and in turn has $O(d)$ degrees of freedom per patch solve, where $d$ is the number of degrees of freedom per spacetime cell. Typical implicit (and even some explicit) marching schemes, though, will have to solve a system of $O(nd)$ equations per time step, while this technique will be solving $O(n)$ systems of $O(d)$ equations for an equivalent chunk of spacetime. If we assume a solution can be done in $O(m^3)$ for a linear system with $m$ equations, this means that the typical implicit marching scheme is $O(n^3 d^3)$ while this Spacetime Discontinuous Galerkin procedure is $O(nd^3)$ for the equivalent chunk of spacetime. That's an enormous difference, especially for large problems where $n$ is large!

From here, there are many more benefits. Riemann problems solutions can be found exactly, even in nonlinear cases, since each facet of some spacetime simplex has information either purely incoming or purely outgoing. For parallel implementations, this approach is embarrassingly parallel. For shared memory parallel case, the process is along the lines of:

  1. Grab a local fragment of the mesh incident to some vertex that's a local minima in the spacetime front, lock the faces of this fragment, and send it off to some thread. Note that the front is essentially the space-like manifold that represents the "top surface" of the current spacetime extrusion you've built up

  2. On a given thread, pitch the vertex with its local fragment of simplices and construct the patch. Solve the patch.

  3. Stitch the recently found information into the spacetime mesh, deleting any spacetime cells not needed anymore and updating the front

  4. Perform 1 through 3 across all your threads and vertices until the minimum vertex time exceeds the time you want your simulation to stop at

Other benefits include a variety of adaptive operations that can be done in-place or through the construction of specialized patches, so they still leverage the local problem solving properties and the embarrassingly parallel design.

Empirically, my groups serial code has run faster than a variety of state of the art parallel codes. Our parallel code is more new but has had extremely good scaling efficiency as expected.

Now of course, there are challenges with this technique. If we just consider serial implementation, some key challenges revolve around just implementing the meshing procedure and various data structures needed. This algorithm is actually quite complicated, especially if you want it to generalize to 3dxTime. Once you have the meshing algorithms and data structures in place, a lot of the finite element solving stuff will largely fall into place in a way that is not so different than usual finite element codes. However, adaptive operations can get quite tricky in spacetime, especially for 3dxTime, and complicated both the meshing and finite element side of things. In fact, it is in open problem (that I am working on) to find a provably good policy in 3dxTime that allows for both adaptive refinement and coarsening that ensures we can make progress in spacetime indefinitely.

Another challenge is visualization because once you get to 3dxTime, you cannot directly visualize patches. Time-slicing at some desired set of times is always possible, though still another challenge because slicing some spacetime simplex for some constant time doesn't always produce a simplex in space (imagine slicing a 4-simplex such that 2 vertices are above the desired time and the other 3 are below.. what do you get?).


In any event, I hope you've got a better idea of how this works and why it could be advantageous and also a challenge to use this approach. I should add a note that this approach is useful for all problems that are modeled as hyperbolic systems of equations. My group and some collaborators have some related work to converting other PDEs into hyperbolic PDEs so we can use them in this framework. Let's see where the future goes...

In the meantime, let me share with you some work by colleagues related to this:

$\endgroup$
  • 1
    $\begingroup$ I always envisioned space-time FEM as applying uniform multi-step time discretizations that couple DOF’s in time so that all dof’s conform at given timesteps. I never envisioned meshing time and space in a 4-d manifold! $\endgroup$ – Paul Apr 7 at 18:35
  • $\begingroup$ @Paul: I know. It really is an odd, but cool, thing. This technique really goes against the typical algorithmic approach AND it ends up actually being efficient relative to typical approaches.. who would have guessed higher dimensions would save work in this context! $\endgroup$ – spektr Apr 7 at 18:39
  • $\begingroup$ It would be a better answer if you discuss other space-time f.e. methods beyond the discontinuous Galerkin since the original question was more general. Not that I dislike your description, its great $\endgroup$ – VorKir Apr 7 at 19:40
  • $\begingroup$ @VorKir: Yeah you are right that the original question was more general. Since the OP mentioned elastodynamics and fluids, I felt like focusing on this method I know well for hyperbolic PDEs would be fine even if it isn't a complete answer to their question. I am not as well versed on the other techniques unfortunately, so I think it would be better if someone else commented on those. $\endgroup$ – spektr Apr 7 at 21:23
  • 1
    $\begingroup$ @spektr: Thank you very much for your answer! Although I would like to know more on the applications side in elastodynamics and fluid dynamics, your answer convinced me that it is really worth it. Thank you very much for your effort. $\endgroup$ – bcoueraud87 Apr 8 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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