What is the best iteration method used in finite element software?

Question

Finite element analysis software uses iteration to find displacement vector. There are many methods like multigrid and conjugate gradient methods. Which is the best method to iterate the required vector so that the computation time taken is minimized?

Answer 1

There are different types of iterations used in finite element solvers.

1. Iterations due to nonlinearity. Finite element methods cannot usually directly deal with nonlinear problems and hence the problems are linearized. This leads to iterative methods such as Newton's method or fixed point method.

2. Iterations for solving in time. The most typical approach is to use a finite difference method in time and finite element method in space. For this approach we need an initial guess and an iteration over time steps. The list of such methods include explicit Euler, implicit Euler, Runge-Kutta and Crank-Nicholson.

3. Iterations for solving the resulting linear systems $Ax=b$.

Number 3 is probably the one that you are concerned with in this question. The best method depends on the properties of the matrix $A$: there is no single method which works for every case.

Standard iterative method for symmetric matrices (also in applications other than FEM) is the conjugate gradient method. For finite element analysis, this is usually coupled with various preconditioners in order to obtain the solution in a smaller amount of steps. A good black box preconditioner is provided by the incomplete Cholesky factorization.

For nonsymmetric problems the iterative solvers generally require more iterations to finish. Methods include GMRES and BiCGSTAB. Preconditioners should be used if possible, but I don't know enough of nonsymmetric preconditioners to comment on this.

Multigrid methods are based on the idea of iterating with multiple grids/meshes. The high oscillatory component of the solution can be solved very quickly using a dense mesh and few steps with a simple iterative method such as Jacobi iteration or Gauss-Seidel method. The low oscillatory component can be solved using coarser grid and possibly even using a direct method (non-iterative solution methods such as Cholesky or LU decomposition). These different methods for different grids/meshes are combined to obtain the solution quickly.

Algebraic multigrid method is a black box method that requires no knowledge of the underlying equations. Geometric multigrid methods require knowledge of the underlying partial differential equation. They may give you more performance but require more effort to implement.

AFAIK, geometric multigrid method (when applicable) is generally considered to be one of the fastest methods for solving discretized PDE's. However, usually I have seen these applied to very simple PDE's (say, Poisson equation) only.