[Fluent Inc. Logo] return to home search
next up previous contents index

25.6.3 Algebraic Multigrid (AMG)

This algorithm is referred to as an "algebraic'' multigrid scheme because, as we shall see, the coarse level equations are generated without the use of any geometry or re-discretization on the coarse levels; a feature that makes AMG particularly attractive for use on unstructured meshes. The advantage being that no coarse grids have to be constructed or stored, and no fluxes or source terms need to be evaluated on the coarse levels. This approach is in contrast with FAS (sometimes called "geometric'') multigrid in which a hierarchy of meshes is required and the discretized equations are evaluated on every level. In theory, the advantage of FAS over AMG is that the former should perform better for non-linear problems since non-linearities in the system are carried down to the coarse levels through the re-discretization; when using AMG, once the system is linearized, non-linearities are not "felt'' by the solver until the fine level operator is next updated.



AMG Restriction and Prolongation Operators


The restriction and prolongation operators used here are based on the additive correction (AC) strategy described for structured grids by Hutchinson and Raithby [ 151]. Inter-level transfer is accomplished by piecewise constant interpolation and prolongation. The defect in any coarse level cell is given by the sum of those from the fine level cells it contains, while fine level corrections are obtained by injection of coarse level values. In this manner the prolongation operator is given by the transpose of the restriction operator


 P = R^T (25.6-9)

The restriction operator is defined by a coarsening or "grouping'' of fine level cells into coarse level ones. In this process each fine level cell is grouped with one or more of its "strongest'' neighbors, with a preference given to currently ungrouped neighbors. The algorithm attempts to collect cells into groups of fixed size, typically two or four, but any number can be specified. In the context of grouping, strongest refers to the neighbor $j$ of the current cell $i$ for which the coefficient $A_{ij}$ is largest. For sets of coupled equations $A_{ij}$ is a block matrix and the measure of its magnitude is simply taken to be the magnitude of its first element. In addition, the set of coupled equations for a given cell are treated together and not divided amongst different coarse cells. This results in the same coarsening for each equation in the system.



AMG Coarse Level Operator


The coarse level operator $A^H$ is constructed using a Galerkin approach. Here we require that the defect associated with the corrected fine level solution must vanish when transferred back to the coarse level. Therefore we may write


 R \, d^{\rm new} = 0 (25.6-10)

Upon substituting Equations  25.6-2 and 25.6-8 for $d^{\rm new}$ and $\phi^{\rm new}$ we have


$\displaystyle R \, \left[A \, \phi^{\rm new} + b \right]$ $\textstyle =$ $\displaystyle 0$  
$\displaystyle R \, \left[A \, \left(\phi + P \, \psi^H\right) + b\right]$ $\textstyle =$ $\displaystyle 0$ (25.6-11)

Now rearranging and using Equation  25.6-2 once again gives


$\displaystyle R \, A \, P \, \psi^H + R \, \left(A \, \phi + b\right)$ $\textstyle =$ $\displaystyle 0$  
$\displaystyle R \, A \, P \, \psi^H + R \, d$ $\textstyle =$ $\displaystyle 0$ (25.6-12)

Comparison of Equation  25.6-12 with Equation  25.6-7 leads to the following expression for the coarse level operator:


 A^H = R \, A \, P (25.6-13)

The construction of coarse level operators thus reduces to a summation of diagonal and corresponding off-diagonal blocks for all fine level cells within a group to form the diagonal block of that group's coarse cell.



The F Cycle


The multigrid F cycle is essentially a combination of the V and W cycles described in Section  25.6.2.

Recall that the multigrid cycle is a recursive procedure. The procedure is expanded to the next coarsest grid level by performing a single multigrid cycle on the current level. Referring to Figures  25.6.1 and 25.6.2, this means replacing the square on the current level (representing a single cycle) with the procedure shown for the 0-1 level cycle (the second diagram in each figure). We see that a V cycle consists of:

 \mbox{pre sweep} \rightarrow \mbox{restrict} \rightarrow \mb... ...e} \rightarrow \mbox{prolongate} \rightarrow \mbox{post sweep}

and a W cycle:

 \mbox{pre sweep} \rightarrow \mbox{restrict} \rightarrow \mb... ...e} \rightarrow \mbox{prolongate} \rightarrow \mbox{post sweep}

An F cycle is formed by a W cycle followed by a V cycle:

 \mbox{pre sweep} \rightarrow \mbox{restrict} \rightarrow \mb... ...e} \rightarrow \mbox{prolongate} \rightarrow \mbox{post sweep}

As expected, the F cycle requires more computation than the V cycle, but less than the W cycle. However, its convergence properties turn out to be better than the V cycle and roughly equivalent to the W cycle. The F cycle is the default AMG cycle type for the coupled equation set.



The Flexible Cycle


For the flexible cycle, the calculation and use of coarse grid corrections is controlled in the multigrid procedure by the logic illustrated in Figure  25.6.3. This logic ensures that coarser grid calculations are invoked when the rate of residual reduction on the current grid level is too slow. In addition, the multigrid controls dictate when the iterative solution of the correction on the current coarse grid level is sufficiently converged and should thus be applied to the solution on the next finer grid. These two decisions are controlled by the parameters $\alpha$ and $\beta$ shown in Figure  25.6.3, as described in detail below. Note that the logic of the multigrid procedure is such that grid levels may be visited repeatedly during a single global iteration on an equation. For a set of 4 multigrid levels, referred to as 0, 1, 2, and 3, the flex-cycle multigrid procedure for solving a given transport equation might consist of visiting grid levels as 0-1-2-3-2-3-2-1-0-1-2-1-0, for example.

Figure 25.6.3: Logic Controlling the Flex Multigrid Cycle
figure

The main difference between the flexible cycle and the V and W cycles is that the satisfaction of the residual reduction tolerance and termination criterion determine when and how often each level is visited in the flexible cycle, whereas in the V and W cycles the traversal pattern is explicitly defined.

The Residual Reduction Rate Criteria

The multigrid procedure invokes calculations on the next coarser grid level when the error reduction rate on the current level is insufficient, as defined by


 R_i > \beta R_{i-1} (25.6-14)

Here $R_i$ is the absolute sum of residuals (defect) computed on the current grid level after the $i$th relaxation on this level. The above equation states that if the residual present in the iterative solution after $i$ relaxations is greater than some fraction, $\beta$ (between 0 and 1), of the residual present after the $(i-1)$th relaxation, the next coarser grid level should be visited. Thus $\beta$ is referred to as the residual reduction tolerance, and determines when to "give up'' on the iterative solution at the current grid level and move to solving the correction equations on the next coarser grid. The value of $\beta$ controls the frequency with which coarser grid levels are visited. The default value is 0.7. A larger value will result in less frequent visits, and a smaller value will result in more frequent visits.

The Termination Criteria

Provided that the residual reduction rate is sufficiently rapid, the correction equations will be converged on the current grid level and the result applied to the solution field on the next finer grid level.

The correction equations on the current grid level are considered sufficiently converged when the error in the correction solution is reduced to some fraction, $\alpha$ (between 0 and 1), of the original error on this grid level:


 R_i < \alpha R_0 (25.6-15)

Here, $R_i$ is the residual on the current grid level after the $i$th iteration on this level, and $R_0$ is the residual that was initially obtained on this grid level at the current global iteration. The parameter $\alpha$, referred to as the termination criterion, has a default value of 0.1. Note that the above equation is also used to terminate calculations on the lowest (finest) grid level during the multigrid procedure. Thus, relaxations are continued on each grid level (including the finest grid level) until the criterion of this equation is obeyed (or until a maximum number of relaxations has been completed, in the case that the specified criterion is never achieved).



The Coupled and Scalar AMG Solvers


The scalar AMG solver is used for the solution of linear systems obtained from the discretization of the individual transport equations.


 a_{ij} x_j = b_i (25.6-16)

where the above equation contains scalar variables.

The coupled AMG solver is used to solve linear transport equations using implicit discretization from coupled systems such as flow variables for the density-based solver, pressure-velocity variables for the coupled pressure-based schemes and inter-phase coupled individual equations for Eulerian multiphase flows.


[A]_{ij} \vec{X}_j = \vec{B}_i (25.6-17)

where the influence of a cell $i$ on a cell $j$ has the form


 A_{ij} = \left[\begin{array}{llll} a_{ij}^{11} & a_{ij}^{12}... .... & .\\ a_{ij}^{N1} & & & a_{ij}^{NN} \\ \end{array} \right] (25.6-18)

and the unknown and source vectors have the form
 \vec{X}_{j} = \left[\begin{array}{llll} x_{j}^{1} \\ . \\ . \\ x_{j}^{N} \\ \end{array} \right] (25.6-19)


 \vec{B}_{i} = \left[\begin{array}{llll} b_{i}^{1} \\ . \\ . \\ b_{i}^{N} \\ \end{array} \right] (25.6-20)

The above resultant system of equations is solved in FLUENT using either the Gauss-Seidel smoother or the Incomplete Lower Upper decomposition (ILU) smoother. If a scalar system of equations is to be solved then the point-method (Gauss-Seidel or ILU) smoother is used, while for a coupled system of equations the block-method (Gauss-Seidel or ILU) smoother is used.

Gauss-Seidel

The Gauss-Seidel method is a technique for solving a linear system of equations one at a time and in sequence. It uses the previously computed results as soon as they become available. It performs two sweeps on the unknowns in forward and backward directions. Both point or block method Gauss-Seidel smoothers are available in FLUENT to solve for either the scalar AMG system of equations or the coupled AMG system of equations.

The Gauss-Seidel procedure can be illustrated using the scalar system, Equation  25.6-16. The forward sweep can be written as:


 {x_i}^{k+1/2} = (b_i - \sum_{j < i} {a_{ij}{x_j}^{k+1/2}} - \sum_{j > i} {a_{ij}{x_j}^{k}})/{a_{ii}} (25.6-21)


 (i = 1,...,N)

where N is the number of unknowns. The forward sweep is followed by a backward sweep which can be written as:


 {x_i}^{k+1} = (b_i - \sum_{j < i} {a_{ij}{x_j}^{k + 1/2}} - \sum_{j > i} {a_{ij}{x_j}^{k+1}})/{a_{ii}} (25.6-22)

Following from Equations  25.6-21 and 25.6-22, symmetric Gauss-Seidel can be expressed in matrix form as a two-step recursive solution of the system


 (D_A + L_A)D{_A}^{-1}(D_A + U_A)(x^{k+1} - x^{k}) = b-A{x^k} (25.6-23)

where $D_A$, $L_A$, and $U_A$ represent diagonal, lower tridiagonal, and upper tridiagonal parts of matrix $A$, respectively.

Symmetric Gauss-Seidel has a somewhat limited rate of smoothing of residuals between levels of AMG, unless the coarsening factor is set to 2.

Incomplete Lower Upper (ILU)

A more effective AMG smoother is based on the ILU decomposition technique. In general, any iterational method can be represented as


 M(x^{k+1} - x^{k}) = b - Ax^{k} (25.6-24)

where matrix M is some approximation of the original matrix A from


 Ax = b (25.6-25)

$M$ should be close to A and the calculation of $M^{-1}$ should have a low operation count. We consider $M$ as an incomplete lower upper factorization of the matrix A such that

 M = L U = (D + L_A)D^{-1}(D + U_A) (25.6-26)

where $L_A$ and $U_A$ are the lower tridiagonal and upper tridiagonal parts of matrix A. The diagonal matrix D is calculated in a special way to satisfy the following condition for diagonal $D_M$ of matrix M:


 D_M = D_A (25.6-27)

In this case, the $i$th element of the diagonal of D will be calculated using


 d_{ii} = a_{ii} - \sum_{j<1}(\frac{a_{ij}a_{ji}}{d_{jj}}) (25.6-28)

The calculation of the new solution $x^{k+1}$ is then performed in two symmetric recursive sweeps, similar to Gauss-Seidel sweeps. Diagonal elements $d_{ii}$ of the ILU decomposition are calculated during the construction of levels and stored in the memory. ILU smoother is slightly more expensive compared to Gauss-Seidel, but has better smoothing properties, especially for block-coupled systems solved by coupled AMG. In this case, coarsening of levels can be more aggressive using coarsening factors between 8 and 12 for 3D problems compared to 2 for Gauss-Seidel.

figure   

When solving the coupled systems, shorter solution times and more robust performance can be obtained by using the default ILU smoother, rather than the Gauss-Seidel smoother, which is the default for scalar systems. ILU is recommended whenever the coupled AMG solver is used.


next up previous contents index Previous: 25.6.2 Multigrid Cycles
Up: 25.6 Multigrid Method
Next: 25.6.4 Full-Approximation Storage (FAS)
© Fluent Inc. 2006-09-20