Astron. Astrophys. 324, 161-176 (1997)

5. A nested multigrid RT method

We have used the term "standard multigrid method" to refer to the non-linear multigrid method described above. There is, however, a more efficient way of applying the multigrid technique, which leads to a factor 2 of CPU-time saving with respect to the standard multigrid method. We shall call it "the nested multigrid RT method".

A reader already familiar with the grid-doubling technique developed in Paper I will immediately realize its advantages. That grid-doubling strategy (cf. Paper I) consisted in (a) initialization (e.g. using LTE populations) and then iteration to convergence in the coarsest usable grid, i.e. in the grid of resolution level , (b) interpolation of these populations onto a finer level grid, and then iteration only until the convergence error becomes smaller than the truncation error corresponding to that grid level, and (c) repetition of this last step "jumping" to successively finer grids until a solution with the desired truncation error is reached. An important point for our grid-doubling technique is, therefore, the analytical derivation of formulae (like Eq. (19)) which allow one to estimate the convergence error from the relative changes at each iterative stage "itr ", and the truncation error associated with each grid used.

The method used in Paper I for solving the multilevel non-LTE equations in each grid was the MALI scheme; however, the same grid-doubling technique can be combined with any other multilevel transfer method, like e.g. our MUGA method, or the standard multigrid scheme. What we now call "the nested multigrid RT method" consists in applying our "grid-doubling technique" (cf. Paper I), but using the standard multigrid RT method instead of the MALI scheme for the calculation of the atomic populations at each grid resolution level. Our nested multigrid method for multilevel RT applications has two loops: an outer loop where we sequentially refine the resolution of the grid being used, and an inner loop where we apply the standard multigrid method to find the run of populations on the current grid. The steps are:

(1) On the coarsest usable grid, level , iterate to convergence using the MUGA scheme.

(2) Interpolate the level l populations onto grid level using cubic centered interpolation. Apply standard multigrid iterations in grids of level down to level 1. Iterate only until in the current grid of level, .

(3) Continue this process until the finest grid has been reached or, alternatively, until the desired truncation error is obtained.

A flow chart illustrating the logical structure of our nested multigrid RT code is shown in Fig. 16. In the implementation of this nested multigrid strategy, we always use the norm to calculate and in order to obtain information on the maximum true error of the converged populations. Fig. 17 shows nested iterations with 4 grids for the Ca II reference 1D problem. We deliberately set the stopping criterion for each grid of resolution level at , instead of iterating each grid only until . Thus, this figure demonstrates that the -value of the first multigrid iteration is a good estimate of the truncation error of the previous grid (see also Paper I). Because a parabolic expansion is used for the formal integration of the transfer equation the truncation error decreases cubically as the grid resolution is increased (see Paper I). Therefore, the truncation error of each grid of resolution level "l " can be estimated by

At each l -grid we have to iterate only until C . Therefore, from Eq. (19) we know that we have to iterate only until

Fig. 16. Flow chart illustrating the logical structure of our nested multigrid RT code.

Fig. 17. The variation with the iteration number of (solid lines) and (dashed lines) using four grids of increasing resolution (see labels). The problem treated is the 5-level Ca II 1D case. The vertical dotted lines indicate the zero iteration in each grid. In the coarsest grid of =60 km we initialize with LTE populations. The norm was used.

With this "stopping criterion" we can easily estimate the number of multigrid iterations one actually needs for each grid: one iteration will be enough if , two if and four if . This agrees perfectly with Fig. 17, where one MG iteration is always sufficient to achieve the truncation error at each grid level (note that in our Ca II case the convergence rate is always smaller than 0.1 if .)

The solid line of Fig. 18 shows the convergence behaviour of the nested multigrid RT method as a function of the CPU time measured in units of one standard MG iteration (see the scale at the bottom) and in units of the CPU time required by one MUGA iteration in the finest grid (see the scale at the top). The dashed-line of Fig. 18 corresponds to a calculation performed with the standard MG method. For this four-grid example the CPU-time one can save by using the nested MG method instead of the standard one is about a factor two. Note that, as dictated by our stopping criterion, the iterations are automatically terminated once the truncation error of the finest grid is reached.

Fig. 18. Convergence error of the standard (dashed-line) and of the nested (solid-line) multigrid methods as a function of the CPU time in units of the CPU time of one standard MG iteration (bottom scale) and of one MUGA iteration (top scale) in the finest grid. These are 2D multilevel calculations for our Ca II reference problem with =7.5 km, =31.25 km and for a horizontal periodicity P =750 km. The norm was used.

For a given grid resolution level the truncation error is determined by the accuracy of the formal solver used. That error for the finest grid in Fig. 18 is about 0.1 %, and the CPU time required by our nested MG method to yield the converged solution is approximately the time required to make only 1.5 standard MG iterations (see the scale at the bottom of Fig. 18). The scale at the top shows that the converged solution in the finest grid (where the accuracy is 0.1 %!) is reached in a time similar to that required to perform 6 MUGA iterations, which in turn indicates that the CPU time needed by one standard MG iteration is equal to the time of 4 MUGA iterations. We remind the reader that the cost of one MUGA iteration is virtually identical to the cost of one MALI iteration and that, unless NL is very large, this computational work is dominated by the cost of one formal solution (for all the atomic-model transitions).

The nested multigrid multilevel RT method presented here (either for 1D, 2D or 3D applications) is very fast, since even in very fine grids it provides the converged solution in few () formal solution times. To stress this point, we note that in Fig. 12 of Paper I we showed an example of a 2D multilevel calculation for Ca II applying our grid-doubling technique (combined with the MALI scheme) for a four-grid case. For that particular four-grid example, our nested multigrid RT technique is four times faster that the MALI-based nested-grid method of Paper I. We further note that the higher the resolution level of the finest-grid the larger the CPU-time gaining factor with respect to our MALI-based grid-doubling technique of Paper I.

© European Southern Observatory (ESO) 1997

Online publication: May 26, 1998

helpdesk.link@springer.de