Phenomenological comparison of different AMG approaches for
the finite element analysis in surgery simulations

Jens G. Schmidt
C&C Research Labs, NEC Europe Ltd.
Rathausallee 10 53757, Sankt Augustin, Germany
schmidt@ccrl-nece.de

We are dealing with the simulation of maxillo-facial surgeries, especially with distraction osteogenesis. During this treatment the surgeon cuts free the upper jaw (maxilla), which is subsequently relocated into a new position with a distraction device in the course of several weeks. Our simulation tool is set up to predict the displacements of the facial tissues during and after the pulling process and is based on individual CT images of the patient's head before treatment. Its purpose is to support the surgeon in optimizing the treatment plan and avoiding additional post operative plastic surgeries.

The input data for the simulation task is generated by adding the suggested cuts, the geometry of the distraction device and the suggested forces to the CT data of the patient's head. From these data we generate a Finite Element mesh of the head and perform a Finite Element analysis of the distraction process. In order to achieve sufficient accuracy we have to resolve most of the geometrical features of the human head, which leads to a large number of unknowns, typically several millions. In addition to that the computational costs are significantly increased by the finite displacements which can only be properly approximated by non-linear modeling. The resulting systems of equations must be solved on high performance computing resources, such as parallel or vector machines.

Focusing on the efficiency of the Finit Element simulation, the linear solver used to solve the arising systems of equations plays the most crucial role. In our case standard solvers like Krylov methods or ILU methods fail, as we will show in our presentation. Therefore we will focus on the use of Multigrid solvers.

But the complex geometry of the human head in combination with large jumps of the material parameters - Young's modulus jumps about 5 orders of magnitude between bone and soft tissues - prevents standard multigrid approaches to converge at a sufficient rate. In theory they can be dramatically improved by computing the ``near null space'' of the systems, consisting of the all quasi-rigid body modes, and treat it separately. But we will show, that for our problems a basis of this space needs approximately 10 times the memory of the linear system itself, which rules out this approach.

In our presentation we will demonstrate the performance of the only two solvers we have found to work on our problems so far, which are BoomerAMG from LLNL's HYPRE package and ML from Sandia's Trilinos package. We will show the results of our intensive parameter studies and discuss the extensibility of our performance results for elasto-mechanical Finite Element simulations in general.