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

4. Efficiency

The analysis of the previous section has shown that the convergence rate of the multigrid method is very high and does not deteriorate when the discretization is refined; however, it says nothing about the efficiency of the multigrid method compared to the one of the MALI or MUGA schemes. Each multigrid cycle requires more computation than a single MUGA iteration. As we shall now show the rapid convergence of the multigrid scheme more than compensates for this increased cost per iteration.

We can define the "cost " of a numerical method as the CPU time needed to reduce the error by one order of magnitude. The corresponding "efficiency " is inversely proportional to this "cost ". Since the number of iterations required to achieve a factor of ten improvement is given by Eq. (23), the cost measured in arbitrary units is just

where time is the CPU-time required by one iteration.

A relatively small value of makes the efficiency of the method high. The ratio of the costs of two different iterative methods measures their relative merit. In what follows we will first consider the 1D case, and afterwards the multidimensional one. In each case we will analyze the TG and MG efficiencies.

4.1. The MUGA method

As with the Jacobi-based MALI method of Paper I, each MUGA iteration requires the formal solution of the RT equations and the inversion of the NP_l blocks of dimension NL NL. For not too large values of NL the formal solution time dominates and we can neglect the computational effort required for performing such inversions. Since our formal solvers are based on the short-characteristics technique (cf. Paper I) the computing time per MUGA iteration will be, either in 1D, 2D or 3D, directly proportional to the number of spatial grid points, NP_l. Thus, the cost of the GS-based MUGA method of TF-2 (measured in arbitrary units) is approximately given by

From Fig. 9 we know that as the spatial resolution of the grid is improved . It is this deterioration of the convergence rate, rather than the increased formal solution time that dominates the cost of MUGA iterations on fine grids. In fact, this same drawback is characteristic of all operator splitting methods based on approximate operators which are constructed as a direct simplification of the full operator corresponding to a single grid.

4.2. Two-grid method

The computational work done in a two-grid iteration is composed of the following contributions:

On the finest grid (l) one performs " " smoothing iterations using the MUGA method, and one formal solution for the radiation field in order to calculate the residual for the current estimate. Each MUGA iteration requires one full formal solution and the inversion of NP_l blocks of dimension NL NL. For not too large values of NL we can neglect the computing time required to invert these blocks; thus, the computing time of a two-grid iteration will be

We shall refer to this fine- grid computing time as the "smoothing time ".

In the coarse grid, with resolution level (), one uses MUGA iteration to solve the coarse-grid Eq. (14) plus one formal solution to calculate the rhs of this equation. As pointed out above, for this coarse grid we only need an approximate solution; in fact, experience has shown it is sufficient to reduce the error of the initial estimate only by an order of magnitude. The computing time corresponding to the work done in the coarse grid is the time needed to reduce the error in this grid by this factor, as defined by Eq. (26), but for a grid of level " ", i.e.

where is the coarse-grid reduction factor ( in 1D). We shall refer to this time simply as the coarse solution time.

Accordingly (cf. Eq.  25), the cost of the TG iterative scheme is

Fig. 12a compares the cost of the two-grid and MUGA methods (Eqs.  29 and 26) for a range of spatial grids. These results are for the Ca II multilevel 1D problem of Paper I. The TG method was applied using always two smoothing iterations (i.e. ). The figure shows that TG method is more efficient than the MUGA scheme, especially on very fine grids (i.e., for km).

Fig. 12. a The cost of the MUGA and TG (with ) methods as a function of the fine-grid spacing. b The ratio of the efficiencies of both methods versus the fine-grid spacing for different values: dashed-line (), solid-line (), and dotted-line ().

Fig. 12b shows the ratio of the TG to MUGA efficiencies as a function of the spatial resolution of the grid. In coarse grids (i.e. for km) the TG method does not lead to a significant CPU-time saving with respect to the MUGA method. In fact, the MUGA method (cf. TF-2) is definitely superior for these 1D grids because in practice MUGA is always combined with acceleration techniques that enhance the performance of the MUGA method by at least a factor 2 (see TF-2). The relative efficiency of TG iteration improves as the spatial resolution is refined, but as shown in Fig. 11b that ratio tends to a constant value implying that in 1D the CPU-time saving with respect to the pure MUGA method (i.e. without combining it with acceleration techniques) is at most a factor 3.

The previous results can be understood after analyzing in more depth Eq. (29). The "smoothing time" (cf. Eq.  27) will dominate if (cf. Eq.  28) is small enough that

This occurs when the resolution needed in the fine grid is low. Taking and , this inequality is well satisfied for grids with such that . For the Ca II model problem we are considering this relation is satisfied for grids with km (cf. Fig. 9). Noting that , we find that, in this limit, the cost of the TG method is . This value is similar to the MUGA cost (cf. Fig. 12a) so one does not save a significant CPU-time by using TG instead of MUGA for these 1D grids.

In fine grids, however, most of the time is used in solving the error equation and the relative merit of the TG method with respect to our MUGA method is

From Fig. 9 it can be deduced that, as the spatial resolution of the fine grid is increased, tends to a constant value (0.6 in this Ca II case). Therefore, the CPU time one can save in 1D calculations by using the TG method tends to a constant value equal to 0.3, which agrees with the results plotted in Fig. 12b.

We now consider the dependence of the TG efficiency on . Eq. (29) allows one to determine the optimum value. In the previous section we pointed out that in the TG method decreases with increasing (see Fig. 10b), but that the variation will only be significant in coarse grids, where the smoothing capability of the GS-based MUGA method is not as great as in fine grids. In the coarse-grid regime (i.e. for km) the dependence of on the number of smoothing iterations is proportional to (see Fig. 10b), and the TG cost is

By minimizing this function with respect to one finds that it has a minimum at and strongly increases for . In Table 1 one can see that the optimum value of will indeed be 3 in the coarsest grids, but that it decreases to =1 in the finest grids where the CPU time is dominated by the coarse grid solution time. In this fine-grid regime, where the dependence of on is very small, the efficiency does not depend too much on . We have found, in fact, the use of gives nearly optimal behaviour for all the grid levels.

Table 1. The cost of the TG method (cf. Eq. 29) and of the MUGA method (cf. Eq. 26) for different values of and .

4.3. Multigrid method

As in the two-grid method the time required to perform a multigrid iteration is given by the smoothing time plus the coarse time, i.e. . For the MG method one has more than two grids, and one must make a computational effort equivalent to () MUGA iterations in all the grids except the coarsest. The smoothing time is, thus,

where N is the number of grids used (e.g. N =2 in the TG method).

The coarse solution time is the time one needs to solve Eq. (14) in the coarsest grid, of level . Using the MUGA method to reduce the error one order of magnitude in this grid, the coarse solution time is approximately given by

Adding both times, the total cost of the multigrid scheme is

We can now compare the relative importance of the smoothing and coarse times in the Ca II reference 1D problem. In order to obtain the coarsest solution time tcs (Eq.  32) we use the values of shown in Fig. 9. In Fig. 13 one sees that in very fine grids the coarsest time tcs is larger than the smoothing time tsm, independently of the number of grids chosen, while in coarse grids the CPU time of one MG iteration is dominated by the smoothing time. It is also worth noting that the values such that depend on the number of grids. With (see the TG discussion in the previous section) the tcs time dominates for grids having km; however, with and this only occurs for km.

Fig. 13. The coarsest solution time (cf. Eq. 32) as a function of the spatial resolution of the finest grid for the 1D Ca II problem. Each labeled curve corresponds to a different total number of grids chosen. The horizontal lines show the smoothing time (cf. Eq. 31) associated with different choices of . Since appears as a proportionality factor in Eqs. (31) and (32), the times given in this figure have been multiplied by .

Therefore, in practice, when one uses four or more grids, the time needed to solve the coarse grid Eq. (14) is always smaller that the smoothing time, and we can approach the MG cost by

which demonstrates that the MG cost is simply proportional to . Note that, if we use a high number of grids, in this 1D case. For the Ca II problem we have found (with ) that for all resolution levels "l". Therefore, we have as an upper limit

which is an inequality valid even for very small values of , but only for calculations using a large number of grids.

Accordingly, the time improvement of the MG method with respect to MUGA (cf. Eqs.  34 and 26) is given by

Since the dependence of with the spatial resolution of the finest grid is very small, the CPU time one can save with the MG method is proportional to (i.e. inversely proportional to the number of iterations needed to solve the problem with the MUGA method). This conclusion reveals the main advantage of the MG method with respect to other iterative methods: the MG efficiency is limited only by the CPU time needed to make a single formal solution of the RT equation, but not at all by the number of iterations required to achieve the correct converged solution, since this number will be always very small, and basically independent of the spatial resolution required for solving a given problem. For the Ca II multilevel transfer problem considered here (see Fig. 9); therefore, when many grids are being used

Fig. 14 (with the detailed description given in its caption) clearly illustrates what we have just discussed. In addition, it also shows that, at it was also the case for the TG method, an optimum behaviour is always obtained by taking smoothing iterations.

Fig. 14. The cost of the multigrid (MG) method (a) and the ratio of the costs of the MG and MUGA methods (b) versus the fine-grid resolution level. Dotted line (), solid line (), dashed-dotted line () and dashed-double-dotted line (). The numbers on the steps drawn in the upper part of a refer to the number (N) of grids used for each finest-grid resolution level. N was chosen such that in the coarsest grid we had at least one point per density scale height.

We end this section by pointing out that our MUGA method combined with standard acceleration techniques and/or our SOR method (see TF-1 and TF-2) are indeed capable of solving rapidly complicated multilevel problems. Therefore, we conclude that in 1D situations the use of MG is justified mainly for solving non-LTE RT problems in very fine grids ( km), since it is for these very high-resolution problems where MG turns out to be the true winner.

4.4. Results for the multidimensional case.

Unlike the 1D case, the efficiency of the multidimensional MG method is substantially better than methods like MALI (cf. Paper I) or MUGA (cf. TF-2). This follows from the fact that the convergence as a function of grid resolution in multidimensional cases is similar to the 1D case, presented in Fig. 9, but the cost of an iteration falls as a power of the grid resolution, which makes coarse grid computation relatively very cheap. In 3D, for example, a grid with half as many points in each direction requires an eighth as much computer time for a MUGA iteration. This fact plus the increase in the convergence rate as coarser grids are used makes the multidimensional, multigrid approach very effective.

First, consider the application of the two-grid (TG) method to grids sufficiently fine such that the TG iteration is dominated by the coarsest solution time (see Fig. 13). From Eq. (30) we have that the time improvement factor of the TG method with respect to the MUGA method reaches a constant value as the spatial resolution of the grid is increased. However, while this constant value was in the 1D case, it is in 2D and for 3D situations. (Recall that we found it optimum to choose for 1D, for 2D and for 3D applications). This means that one can save, with respect to the pure MUGA method, about an order of magnitude when solving multidimensional RT problems via the application of the TG method.

Second, consider the application of the MG method using a large number of grids (see Fig. 13). In this case, for most grid resolution levels the MG iteration turns out to be dominated by the smoothing time (cf. Eq.  31) and the improvement factor of the MG method with respect to MUGA can be approached by Eq. (36). As an upper limit we have that

with in 2D, and in 3D.

Therefore, in this limit the improvement in the efficiency by using the MG method is simply the larger the finer the grid (i.e. the closer to unity the value of ). For instance, for (which according to Fig. 9 it occurs for km for the Ca II problem) one already finds almost an order of magnitude of CPU-time saving with respect to the pure MUGA method. As the spatial resolution is improved, the time one can save grows continuously, simply because as the discretization is refined.

In order to illustrate the performance of the MG method for multidimensional situations we show in Fig. 15 some results of 5-level Ca II calculations for a two-dimensional model atmosphere. As in Paper I, we have assumed that the temperature is fluctuating sinusoidally along the horizontal x-direction with an amplitude of 500 K and with different horizontal periodicities (P) (see Paper I for more details). For each of the two values selected we have performed MG and MUGA calculations using two different values for the horizontal grid spacing . The maximum number of grids was chosen according to the criterion that in the coarsest grid should never become larger than unity (with the density scale height), and that the coarsest grid must at least have three points per horizontal period. As it can be seen in Fig. 15 the improvement factor for 2D situations can indeed be very much larger than for the 1D case discussed above, especially if the grid is very fine. We conclude that the solution of complicated 2D and 3D multilevel problems with scalar-class computers can be done much more efficiently using our multigrid RT code than with our MALI or MUGA multidimensional codes, and with a saving factor which is the larger the higher the spatial resolution of the 2D and/or 3D grids required.

Fig. 15. The convergence error of 2D multilevel calculations for Ca II versus the CPU-time measured in units of the CPU-time required by one MUGA iteration in the finest grid. Each figure is for different values of and P, where P is the periodicity of the horizontal temperature inhomogeneities. They show the MUGA method, MUGA combined with Ng acceleration, and the MG method. All the cases were calculated with and with 25 horizontal points per horizontal period.

© European Southern Observatory (ESO) 1997

Online publication: May 26, 1998

helpdesk.link@springer.de