Monday, January 4, 2021

Mixed FEM and constrained dynamics

 I recently got a paper accepted, which in itself was an achievement and culmination of a long period of work, hardship and even failures. But the idea I want to bring forward in this post is that the paper only scratches the surface of the implications it can have and could be developed further. Such is the way of academic publishing: not always the results I or you deem important are considered results worth publishing by the academic community. And I won't go that far into saying that my results were revolutionary. I'm merely saying that they are interesting and they may settle a decades-long debate in the engineering, graphics and simulation circles.

But let me tell you more before I get to that. The mixed formulation of the finite element method (FEM) is a technique that has been around at least from the 70's. Its main purpose was to solve incompressible problems in fluid flow and elasticity. This was due to a problem called locking that is still affecting our simulations. As a simple example, locking happens when you simulate a cantilever bar bending under some load; and although you know it should deflect by quite a bit, the numerical results tell you the deflection is zero or very close to zero. But let's not worry about locking, as even if avoiding it may seem like the main result, I argue that it isn't.

The main achievement of mixed FEM is its beauty and unifying power. So what is it? I will make an analogy with springs. The opposite of mixed FEM is irreducible FEM, or I call it standard FEM, because it's used all over the place. Spring forces (like stresses in a finite element) are given by a constitutive law like Hooke's law: the elongation times a spring constant. These forces are then plugged in some equilibrium conditions or Newton's second law to obtain a simulation of the system. The main takeaway here is that you always need a constitutive law of some sorts besides the laws of statics and dynamics to completely determine the behavior of a mechanical system.

What if we don't substitute the constitutive law into the equations of mechanics as we usually do? We get the mixed formulation of springs, and FEM and everything else. We just get (roughly) double the number of equations that we need to solve, but the problem is essentially the same. In fact, it can be argued this formulation is "more" fundamental, and the irreducible form is one that has been reduced from it (and cannot be reduced any further). But why wouldn't you substitute and reduce the equations? Apparently, no reason at all.

This takes us a long lasting debate between choosing reduced coordinates over maximal coordinates. That is, if a system is constrained in any way (like a pendulum attached to a point) then it makes complete sense to consider that some degrees of freedom were removed by the constraints and use only the remaining ones. Or not... The view of constrained dynamics is that you should still use all the initial degrees of freedom of the pendulum and add extra equations and variables for each constraint. Understandingly, a lot of people don't like this, especially in their computer implementations. But it just so happens that this is the best way to simulate constrained dynamics when you don't know from the start what the constraints will be (i.e. model an arbitrary system).

On the other hands, constraints are only ideal and do not really exist in nature. They are just really strong forces in the end. So, there is a middle way: use all the degrees of freedom and model constraints using very very strong forces (like the ones in springs). This keeps the number of variables and equations in the middle. It is also the standard or irreducible form.

But something quite bad happens when the spring constants grow very large. In theory they should tend to infinity so that the constraints are exactly fulfilled. And this is not possible in practice. Numerics become ill-conditioned and, on top of it, extra problems appear like locking. And these won't go away by just putting more power into the number crunching. You need to roll back to the reducible or mixed form of the equations. Or the one that had both constraint equations and equations of motion. You need to make the problem larger in order to make it solvable. And here comes the big revelation: the constitutive laws in the mixed formulation are just soft constraints in constrained dynamics.

And of course people knew about it. At least many do or have a strong intuition about it. But the rest act as if they don't. There are actually two camps in solving contacts and other topics which divide the world into penalty vs. constraint formulations. When they are in fact two sides of the same coin. In their defense, the constraint camp does assume that their constraints are infinitely hard which is not possible when using finite spring constants or material parameters (and despite being ill-conditioned their problems are still solvable, even if by a bit of cheating). But the mixed formulation is just a place where these two different views of the world meet. In technical terms it is called a saddle point problem and keeps popping up whenever you do simulation (see Strang's textbooks for example). And optimization people have known it for a long a time: they call it the KKT optimality conditions. For them the degrees of freedom of the system are the primal variables and the tensions inside the springs are dual variables or Lagrange multipliers.

My personal breakthrough was to show that any simulation problem, no matter how complex (including PDEs), can be formulated as such a mixed formulation involving both the equations of motion and the soft constraints (aka constitutive laws). If any of the constraints needs to be hard, we just put a zero value next to it and everything still works. So, we can build a single unified solver for all mechanical phenomena, including say FEM and contacts, by using the same framework. Of course, that doesn't mean it will be optimal; but sometimes elegance and generalization is better than some optimizations here and there.

And, ok, you would argue, this was still known. Yes, yet nobody used that knowledge. For example, you can build a whole multibody simulator by just treating every constitutive law used as a soft constraint and then use a single constraint solver like XPBD (or a more accurate one, I don't care). Or you can use very stiff springs (the penalty approach) as long as you find a nice stable way to solve the problem. And in the end it may not even matter as optimization theory is already using techniques that rely on both facets of the problem, like the augmented Lagrangian method. You add a bit of penalty, a bit of constraints and you get to solve your problem efficiently.

So what's left to do? I would say a lot. We need to build these unified multibody simulators using the mixed framework and see how they perform. What is the best approach for solving them? Sometimes, you have to pay a bigger price or be a bit slower than the state of the art to reach this degree of generality. Also, pay attention to traps like locking, which become visible in the mixed formulation, but require deep changes at the discretization level in order to be fixed. Overall, I would say it gives us a much higher vantage point on things. What else? Maybe people using implicit integration of stiff springs will stop claiming that they are doing a very different thing from people using constraints. Or claiming you can not simulate some fancy nonlinear dynamics using constraints (which you can by using the three field mixed formulation). Or constraint people realizing that regularization is good from time to time, that relaxation solvers like Gauss-Seidel are in fact already doing it and that not every problem is a nail. And that at some point you can write a solver that takes the best of both worlds. For example, one that tackles high stiffness through constraint solvers and large mass ratios through primal solvers (at the same time, in a single pass, inside one monolithic hybrid solver).