Magic behind the Most of the CFD solvers for HPC

The Need for Speed

Governing equations of the fluid flow problems should be discretized (for example, finite volume, finite element and finite difference) in order to get a good solution (approximation). Discretization has as results system of linear algebraic equations which depend on the problem domain and complexity of the problem. Any standard procedure could be used to solve this system of linear algebraic equations with help of the availability of the computer power but we are always interested in fast and accurate solution with reasonable computer resource. There are two standard methods available to solve the system of linear algebraic equations [1]. These methods are:

1) Direct methods (for example, LU decomposition, Cholesky factorization and Gaussian elimination methods)

2) Indirect or iterative methods (for example, Newton’s method, Bisection, Jacobi and Gauss-Seidel methods)

Generally, in the case of the direct methods, finite numbers of steps are required to solve the system of linear algebraic equations. For example, if the equation is order of 3 and with 3 unknowns then the 3³ number of the operation is needed in order to calculate the solution and also 3³ core memory is required to store co-efficient of the equations. [1]

All the iteration methods start with the initial guess and consecutively progress until it reaches to the original solution. In the case of the iterative methods the number of steps is unpredictable and also the solution of the method depends on the uniqueness and existence of the equations (for example, diagonally dominant, symmetric and positive definite matrix). But the iterative methods are a good option for the spare matrix (most of the entries will be zero in the matrix) where non-zero elements can be stored in the core memory. Moreover, the iteration can be terminated at any time according to the residual error r = b – Ax  even though the number of the iterations is unpredictable. [1]

Multigrid Technique (Short Introduction)

Even though iterative methods require less memory it should be quicker to get a solution. A Jacobi and Gauss-Seidel methods convergence rate is depend on the size of the matrix for example, if the equation increases (finer mesh) the iteration will also increase. Jacobi method is still slower than the Gauss-Seidel because Jacobi does not use the new values that it has computed. This new computed values will be used for the next cycle of calculation. Whereas in Gauss-Seidel the new computed values are updated consecutively for the present cycle of calculation. Multigrid Technique is a procedure or technique that helps the stationary iterative method to enhance their convergence rate. [2]

Typically some stationary iterative methods would reduce the high-frequency (i.e., oscillatory) errors but fails to reduce the low-frequency (i.e., smooth) errors thus will results poor rate of convergence. High-frequency and low-frequency are the names of the errors that are referring to the error in the coarser and finer mesh. In the case of the iterative methods, the solution in the finer grid looks smoother but if we transfer the solution to the coarser grid it will be oscillating. To solve this problem we need to do sampling of the solution from finer grid to coarser grid where a few iterations (iterative methods for example, Gauss-Seidel) need to be done to reduce the high-frequency error. Transferring the solution from finer grid to coarser grid is called restriction. After the few steps of the restriction are done, the error of high-frequency will be reduced. Later this solution is transferred to finer grid for further calculation and by then the low-frequency error is also minimized. Transferring the solution from coarser grid to finer grid is called the prolongation or interpolation. On the finer grid it is suggested to do a few more iterations to keep the high-frequency error still small. So the solution that is in the finer grid will be having less high-frequency and less low-frequency error. These cycles have to be continued until the solution meets the desired convergence criteria. Prolongation, restriction and less iteration in the finer grid gives a faster convergence rate and quicker solution than the normal stationary iterative methods. [2]

For example, the equation Ax = b is to be solved. Initial guess of x with few iterations (for example, Gauss-Seidel) in the finer mesh we will get new approximated value of xx. Now the residual is r = b – Axx and the error is e = x – xx. Error and residual are all together can be written as Ae = r. To improve the approximation of the solution we can just work here after with “residual equation” which has error and residual; without using the b vector of the original equation. [2]

Many types of cyclic schemes are available for the multigrid technique but Figure 1. shows the three standard procedure of multigrid cycles. In Figure 1. the iterations in V-cycle starts with the initial guess in finer mesh later it travels to coarser mesh before it reaches the finer mesh. Computational cost is less for the iterations in the coarser level. W-cycle in Figure 1. goes like zigzag before it reaches the finer mesh. The full multigrid method in Figure 1. shows that the initial iteration starts with coarser level mesh and continues as a V-cycle. [2]

Most of the CFD solvers are working with multigrid methods. For example, Open FOAM has different type of multigrid methods that can be selected by the user while doing the simulation and in Ansys Fluent the user can choose the multigrid method according to the problem type before doing the simulation; as a default it uses the V-cycle multigird method.

Multigrid solvers further classified into two types [3]:

1) Geometric multigrid -FAS: when the solution is transferred to coarser mesh the domain should be re-meshed to have coarser mesh. This method does not work well for example, in the case of the finite volume method.

2) Algebraic multigrid- AMG: calculation will be carried out using the matrix coefficient, for the coarser mesh matrix coefficient will be formed by using the previous matrix information. Hence there is no need of doing the coarser mesh in the problem domain again.

What has this to do with my project

I am using the CFD as a tool to predict and analyze the wind loading on the solar trackers. Once the problem domain is created (geometry design) it needs to be meshed to have sub-domain for the discretized equations to solve the problem. Therefore, in my case I am getting about 5 million to 10 million elements in the problem domain that leads to millions of equations. I am using the Ansys CFX for the simulation, it has its own multigrid solver and it chooses the method according to the problem type (for example, boundary condition, solver type and analysis). Because of the multigrid technique I am getting the faster solution if there are no multigrid methods in the solver I need to wait longer time for the desired converged solution.

References

1. H. Versteeg / W.Malalasekera (2007). An Introduction to Computational Fluid Dynamics: The Finite Volume Method, Prentice Hall.

2. Micheal T. Heath (2005). Scientific Computing:An Introductory Survey, Second Edition, McGraw-Hill Education.

3. http://www.cfd-online.com/Wiki/Multigrid_methods