Null space for smoothed aggregation algebraic multigrid

Question

I do not really get the point of null space usage for creating the prolongation operator for smoothed aggregation algebraic multigrid. I know what the null space is per definition and I know that the null space corresponds with the rigid body modes for structural finite-element problems.

But how can I determine the null space and use it for improving the prolongation operator? Is the null space for 3D structural problems not always the same (3 translations along the global axes and 3 rotation around the global axes)?

Some literature which is understandable and does not skip the needed information would be very helpful.

Answer 1

First of all, I find the name "Smoothed Aggregation" a bit misleading, because the method - as I understood it - consists of both smoothing a tentative prolongation operator and implicitly considering the (near-)null-space for constructing the tentative prolongation operator.

In standard algebraic multigrid with linear elasticity, corrections from coarser spaces do not capture the (near-) null space. That is why in Smoothed Aggregation Multigrid Methods (I would prefer the term Null-Space-Capturing Multigrid Methods) prolongation operators with this property are explicitly constructed. For the simpler type of PDEs like a simple Poisson equation, standard algebraic multigrid automatically captures the null-space, which is the 1-vector in this case.

However, you are asking for the null space of 3D linear elasticity. ..Here, the null space consists of the rigid body modes, i.e. six vectors which are concatenated by the vectors for each node. For one node, three vectors $b_1, b_2, b_3$ represent the translation, a simple basis are the three unit vectors. The other three vectors represent the rotation around an (arbitrary) origin (usually the origin of the FEM coordinates are used).

$$ b_4 = [0, -z, y] $$ $$ b_5 = [z, 0, -x] $$ $$ b_6 = [-y, x, 0] $$

So for node $i$ you need to take its coordinates $[x_i, y_i, z_i]$ to compute, e.g. $b_4 = [0, -z_i, y_i]$. Afterwards, you need to concatenate all vectors. So, the null-space is not identical for all FEM models but depends on the coordinates of the nodes.

The final steps consist of smoothing the null space, so it is more compatible with the boundary conditions (this will then be the near-null space, as the null space of properly constrained FEM is trivial) and block-orthonormalization. For these steps you can check the two papers I listed below (The "original" paper [1], a paper with some good diagrams and helpful supplementary material [2]). If you have any additional questions about these steps, I am happy to edit my answer.

[1] Vanek, P., Mandel, J., and Brezina, M.: Algebraic Multigrid by Smoothed Aggregation for Second and Fourth Order Elliptic Problems, Computing, Vol.56, pp.179-196 (1998)

[2] Rasmus Tamstorf, Toby Jones, and Stephen F. McCormick. 2015. Smoothed aggregation multigrid for cloth simulation. ACM Trans. Graph.34 (2015),245:1–245:13