|
Home / Technical Notes / Mesh / Multigrid Method
Multigrid Method
1. Overview
The time to solve the simultaneous linear equations is substantial. If the number of meshes exceeds ten thousand, most of the simulation time will be spent for the meshing.
The multigrid method solves the simultaneous linear equations with multiple sizes of meshes and saves the simulation time.
2. Theory
The Gauss-Seidel method is one of the classical iterative methods to solve the simultaneous linear equations.
It can damp the high-frequency errors quickly. On the other hand, the low-frequency errors are damped slowly.
The multigrid method overcomes this problem by using the multiple sizes of meshes in Gauss-Seidel method.
The coarser meshes are applied to the low-frequency errors, and they are damped. This process is repeated.
At last, the direct method is used for the coarsest meshes to calculate accurately and remove all errors.
|
Grid 1 |
Grid 2 |
Grid 3 |
 |
||
3. Algorithm
The figures above show an meshing example, in which the number of grids is set to 3. First, the meshes of Grid 1 are generated with the user-specified mesh size.
Then the elements are divided into smaller ones shown as Grid 2, and they are divided again into further smaller elements as Grid 3.
Grids 1 and 2 are used to calculate for Grid 3. The errors of Grid 3 are mapped onto Grid 2, and low-frequency errors are damped.
Next, the remaining high-frequency errors are mapped onto Grid 1, and the accurate calculations are performed with the direct method. Then the results are mapped back onto Grids 2 and 3.
This process is repeated 10 to 30 times until it is converged.
To save the memory usage for Grid 1, go to [Model] tab.
Click [Analysis Condition] 
> [High-Level Setting] tab
> [Matrix Solver Type] > select [Iterative method]
The iterative method is applied for the grid 1 calculation and the memory usage is reduced.
4. Sample calculation
In the 3D acoustic analysis, the calculation time of a linear equation was compared between direct method and multigrid method.
The graph below shows the relationship of calculation time and the number of elements. The large number of elements with the direct method makes the calculation time quite long, while the calculation time with the multigrid method is significantly short.
The direct method took 2 hours 20 minutes with 5.5 million elements while the multigrid method only took 18 minutes with 7.6 million elements. The multigrid method is effective if there are many meshes.
Please note, however, that the multigrid method is not always effective. It is worth trying when the calculation is taking significantly long time.
5. 2nd-order Element in Electromagnetic Analysis (Hertz)
The multigrid method explained above is not applicable to the electromagnetic analysis with 2nd-order elements,
the approximate solutions are calculated not by using coarser meshes but by using lower-order elements.
In other words, only one size of meshes is needed because 2nd-order elements are calculated by using the solutions of 1st-order elements.
If the number of grids is set to 1, the analysis is performed exactly in this way. If the number of grids is set to 2,
the calculations are performed with 1) 1st-order elements with coarse meshes, 2) 1st-order elements with fine meshes, and 3) 2nd-order elements with fine meshes, in this order..
6. Tips for Convergence
If the multigrid method doesn't converge or is too slow, try the tips below.
Tip 1: Make the mesh size smaller.
Tip 2: Change the element incremental rate.
Tip 3: Use the 1st-order element (the 2nd-order element is harder to converge than the 1st-order element).
Reference
William L. Briggs, "A Multigrid Tutorial", SIAM