Results of Multigrid for Reaction-Diffusion

Imports

[1]:

from main import inputParameters, runDemo
import logging
logging.basicConfig(level=logging.INFO , format='[%(asctime)s] - [%(levelname)s] - %(message)s')

Set parameters

[2]:

inputParameters()

==================
* DEFAULT VALUES *
==================
LEVELS              = 5
SHOW_GRIDS          = False
DEGREE              = 1
CYCLE               = W
MAX_ITER            = 100
SMOOTHING_STEPS     = 2
SMOOTHER            = Jacobi
OMEGA               = 0.8

Would you like to change some values? (Y/N): y
Number of MG levels (default: 5) = 10
Plot grids (default: False) =
Degree of FE (default: 1) =
Multigrid cycle (default: W; supported: 'V','W') =
Maximum number of MG iterations (default: 100) =
Number of smoothing steps (default: 2) =
Smoother type (default: Jacobi; supported: 'Jacobi','GaussSeidel') =
Relaxation parameter omega (default: 0.8) =

=================
* CUSTOM VALUES *
=================
LEVELS              = 10
SHOW_GRIDS          = False
DEGREE              = 1
CYCLE               = W
MAX_ITER            = 100
SMOOTHING_STEPS     = 2
SMOOTHER            = Jacobi
OMEGA               = 0.8

Demo

Now that the user has inserted the parameters of the multigrid algorithm, we start by solving the two-grid method, refine the grid, solve the three-grid method, etc.

[3]:

runDemo()

[2020-06-21 21:33:27,249] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:27,250] - [INFO] - +    MULTIGRID (LEVELS =  2)              +
[2020-06-21 21:33:27,250] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:27,518] - [INFO] - Number of DoFs: 21 (by level: 8,21)
[2020-06-21 21:33:27,563] - [INFO] - Defect:           5.43e-13
[2020-06-21 21:33:27,564] - [INFO] - GMG iterations:   14
[2020-06-21 21:33:27,564] - [INFO] - Multigrid time:   0.044 s
[2020-06-21 21:33:27,565] - [INFO] - Convergence rate: 1.0005
[2020-06-21 21:33:27,567] - [INFO] - Total time:     318 ms
[2020-06-21 21:33:27,567] - [INFO] -
[2020-06-21 21:33:27,568] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:27,568] - [INFO] - +    MULTIGRID (LEVELS =  3)              +
[2020-06-21 21:33:27,569] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:27,847] - [INFO] - Number of DoFs: 65 (by level: 8,21,65)
[2020-06-21 21:33:27,938] - [INFO] - Defect:           4.54e-13
[2020-06-21 21:33:27,938] - [INFO] - GMG iterations:   15
[2020-06-21 21:33:27,939] - [INFO] - Multigrid time:   0.089 s
[2020-06-21 21:33:27,940] - [INFO] - Convergence rate: 0.9929
[2020-06-21 21:33:27,941] - [INFO] - Total time:     374 ms
[2020-06-21 21:33:27,942] - [INFO] -
[2020-06-21 21:33:27,942] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:27,943] - [INFO] - +    MULTIGRID (LEVELS =  4)              +
[2020-06-21 21:33:27,943] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:28,226] - [INFO] - Number of DoFs: 225 (by level: 8,21,65,225)
[2020-06-21 21:33:28,405] - [INFO] - Defect:           8.66e-13
[2020-06-21 21:33:28,406] - [INFO] - GMG iterations:   14
[2020-06-21 21:33:28,407] - [INFO] - Multigrid time:   0.173 s
[2020-06-21 21:33:28,407] - [INFO] - Convergence rate: 0.9927
[2020-06-21 21:33:28,410] - [INFO] - Total time:     468 ms
[2020-06-21 21:33:28,411] - [INFO] -
[2020-06-21 21:33:28,412] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:28,412] - [INFO] - +    MULTIGRID (LEVELS =  5)              +
[2020-06-21 21:33:28,413] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:28,841] - [INFO] - Number of DoFs: 833 (by level: 8,21,65,225,833)
[2020-06-21 21:33:29,227] - [INFO] - Defect:           6.6e-13
[2020-06-21 21:33:29,228] - [INFO] - GMG iterations:   14
[2020-06-21 21:33:29,228] - [INFO] - Multigrid time:   0.371 s
[2020-06-21 21:33:29,228] - [INFO] - Convergence rate: 0.9986
[2020-06-21 21:33:29,233] - [INFO] - Total time:     822 ms
[2020-06-21 21:33:29,234] - [INFO] -
[2020-06-21 21:33:29,235] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:29,235] - [INFO] - +    MULTIGRID (LEVELS =  6)              +
[2020-06-21 21:33:29,236] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:30,104] - [INFO] - Number of DoFs: 3201 (by level: 8,21,65,225,833,3201)
[2020-06-21 21:33:30,897] - [INFO] - Defect:           6.57e-13
[2020-06-21 21:33:30,897] - [INFO] - GMG iterations:   13
[2020-06-21 21:33:30,898] - [INFO] - Multigrid time:   0.73 s
[2020-06-21 21:33:30,899] - [INFO] - Convergence rate: 1.0079
[2020-06-21 21:33:30,914] - [INFO] - Total time:     1 s 680 ms
[2020-06-21 21:33:30,915] - [INFO] -
[2020-06-21 21:33:30,916] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:30,917] - [INFO] - +    MULTIGRID (LEVELS =  7)              +
[2020-06-21 21:33:30,917] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:33,536] - [INFO] - Number of DoFs: 12545 (by level: 8,21,65,225,833,3201,12545)
[2020-06-21 21:33:35,531] - [INFO] - Defect:           4.27e-13
[2020-06-21 21:33:35,532] - [INFO] - GMG iterations:   13
[2020-06-21 21:33:35,533] - [INFO] - Multigrid time:   1.786 s
[2020-06-21 21:33:35,535] - [INFO] - Convergence rate: 1.0163
[2020-06-21 21:33:35,625] - [INFO] - Total time:     4 s 710 ms
[2020-06-21 21:33:35,626] - [INFO] -
[2020-06-21 21:33:35,626] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:35,627] - [INFO] - +    MULTIGRID (LEVELS =  8)              +
[2020-06-21 21:33:35,627] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:45,121] - [INFO] - Number of DoFs: 49665 (by level: 8,21,65,225,833,3201,12545,49665)
[2020-06-21 21:33:49,748] - [INFO] - Defect:           9.59e-13
[2020-06-21 21:33:49,748] - [INFO] - GMG iterations:   12
[2020-06-21 21:33:49,750] - [INFO] - Multigrid time:   3.791 s
[2020-06-21 21:33:49,751] - [INFO] - Convergence rate: 1.0314
[2020-06-21 21:33:50,001] - [INFO] - Total time:     14 s 374 ms
[2020-06-21 21:33:50,002] - [INFO] -
[2020-06-21 21:33:50,003] - [INFO] - +-----------------------------------------+
[2020-06-21 21:33:50,003] - [INFO] - +    MULTIGRID (LEVELS =  9)              +
[2020-06-21 21:33:50,004] - [INFO] - +-----------------------------------------+
[2020-06-21 21:34:27,930] - [INFO] - Number of DoFs: 197633 (by level: 8,21,65,225,833,3201,12545,49665,197633)
[2020-06-21 21:34:41,596] - [INFO] - Defect:           4.53e-13
[2020-06-21 21:34:41,597] - [INFO] - GMG iterations:   12
[2020-06-21 21:34:41,598] - [INFO] - Multigrid time:   10.005 s
[2020-06-21 21:34:41,598] - [INFO] - Convergence rate: 1.0361
[2020-06-21 21:34:42,537] - [INFO] - Total time:     52 s 535 ms
[2020-06-21 21:34:42,538] - [INFO] -
[2020-06-21 21:34:42,539] - [INFO] - +-----------------------------------------+
[2020-06-21 21:34:42,539] - [INFO] - +    MULTIGRID (LEVELS = 10)              +
[2020-06-21 21:34:42,540] - [INFO] - +-----------------------------------------+
[2020-06-21 21:37:07,533] - [INFO] - Number of DoFs: 788481 (by level: 8,21,65,225,833,3201,12545,49665,197633,788481)
[2020-06-21 21:37:45,600] - [INFO] - Defect:           8.76e-13
[2020-06-21 21:37:45,601] - [INFO] - GMG iterations:   11
[2020-06-21 21:37:45,601] - [INFO] - Multigrid time:   25.034 s
[2020-06-21 21:37:45,602] - [INFO] - Convergence rate: 1.045
[2020-06-21 21:37:49,246] - [INFO] - Total time:     3 min 6 s 707 ms
[2020-06-21 21:37:49,247] - [INFO] -

Results

Refinements

DoFs

Iterations

Computation time

Convergence rate

1

21

14

0.044

1.0005

2

65

14

0.089

0.9929

3

225

14

0.173

0.9927

4

833

14

0.371

0.9986

5

3201

13

0.730

1.0079

6

12545

13

1.786

1.0163

7

49665

12

3.791

1.0314

8

197633

12

10.005

1.0361

9

788481

11

25.034

1.0450

We would expect from the theory that the number of multigrid iterations needed should be constant and thus independent of the number of levels. This property is approximately fulfilled in our simulation. Furthermore, the computation time should depend linearly on the number of DoFs. In the table above, we can see that the computation time doubles as a rule of thumb after each refinement and the number of DoFs quadruples. Thus the time of the multigrid solver depends linearly on the number of degrees of freedom. Note that for us the assembly is a big bottleneck, since it hasn’t been optimized yet.

From the theory of the multigrid algorithm it is known that for an \(H^1/H^1_0\)-elliptic boundary value problem with an \(H^2\)-regular boundary and conformig finite elements on uniformly refined triangulations, the multigrid convergence rate in the energy norm \(\rho_l \leq \rho < 1\) is mesh independent. Therefore with each approximation step, we get a more accurate solution, independent of the number of uniform refinements:

\[\| u^{(k+1)} - u^\ast \| \leq \rho \| u^{(k)} - u^\ast \|.\]

Thus it is being ensured that the multigrid algorithm converges in a certain number of steps, which does not depend on the number of DoFs. In our numerical tests, we didn’t have an \(H^2\)-regular boundary, but it still could be observed that the multigrid algorithm terminated in at most 14 iterations. Hence, there was no real dependence on the number of refinements.