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

3. The convergence rate

A number of important mathematical theorems that demonstrate the convergence of the two-grid and multigrid iterative schemes can be found in Hackbush (1985). Our objective here is, first, to establish a practical and accurate way to measure the convergence rate and, then, to investigate how this quantity depends on the number of smoothing iterations, and resolution levels used. The results of this section refer to 1D multilevel calculations for Ca II. We point out that similar results are obtained for 2D grids with both and scaling proportionately when the resolution is changed.

3.1. Measuring the convergence speed

For a calculation performed in a grid of level l, a useful quantity to measure the rate of convergence is (cf. Paper I, TF-1):

The smaller this number () the faster the method converges, and the smaller the number () of iterations required to reduce the error by one order of magnitude. This number, , is given by (cf. TF-1):

When we say that the convergence rate is very high we actually mean that is very large. Since the multigrid method converges in very few iterations, it turns out that a more practical and accurate way of estimating the convergence rate is

with iter chosen such that . Both definitions (cf. Eqs.  22and  24) give the same result when applied to more slowly convergent methods (such as the MALI and MUGA schemes).

The curves in Fig. 9 were obtained using Eq. (24). Here we show, for the one-dimensional 5-level Ca II reference case of Paper I, the variation of the convergence rate with the grid spacing. This figure demonstrates the two attractive properties of multigrid techniques. First, it is clearly seen that, while the convergence of the MALI and MUGA schemes decreases significantly as the spatial resolution level of the grid is increased, the convergence rate of the two-grid RT iteration method remains roughly constant. Second, the values of our RT two-grid scheme are always very low (e.g., for the Ca II problem for all resolution levels l), which indicates (cf. Eq. 23) that only one iteration suffices to reduce the error by one order of magnitude, i.e. that convergence is reached in very few iterations. Of course, as the grid is refined, the effort needed to solve for the coarse-grid correction increases dramatically. This is not reflected in the value, , which only inform us about the number of two-grid iterations required to reach convergence, and not about the computational work per iteration. In the next section we will consider in detail the true efficiencies of the two-grid and multigrid iterations comparing them with the one of the MUGA method.

Fig. 9. The variation of the convergence rate (cf. Eq. 24) with the spatial resolution level of the grid. The methods used to obtain the solution to the Ca II multilevel 1D problem referred to in the text are the MALI scheme of Paper I, the MUGA method of TF-2 and the two-grid non-linear method with and .

It is important to point out that in 1D we always choose . Although it is true that a smaller -factor saves some computational work when solving the coarse-grid equation (14), the number of smoothing iterations required at the fine-grid turns out to be larger and the total computational work is not improved. This is due to the fact that, as seen in Fig. 5b, the wavelength of the high-frequency error in the fine grid is inversely proportional to ; therefore, the smaller the larger the wavelength of the high-frequency error, and the larger the number of smoothing iterations required to remove it.

3.2. The influence of the smoothing number

As shown in Fig. 3b the larger the number, , of MUGA iterations in the fine grid the smaller the amplitude of the high-frequency spatial components of the current error and residual. Although the smoothing capabilities of our MUGA scheme are very good for all grid resolution levels, the finer the grid the easier it is for MUGA to achieve a given level of error reduction (cf. Fig. 3b). Therefore, one expects that the values decrease as the smoothing number () increases, and in a way that depends on the finest-grid resolution level.

Fig. 10 gives useful information on this point. Besides showing that the convergence rate improves when is increased, it demonstrates that the sensitivity of to the smoothing number is very small for fine grids (i.e. for km), but significant in coarser grids. For coarser grid cases, we get a sizable decrease of with . In fact, , but note that already yields for all grid levels. In the next section we shall show that with one achieves optimal efficiency in the multigrid method.

Fig. 10. a The convergence rate of the TG method versus the fine-grid resolution level for various values of the number () of smoothing steps. b The TG convergence rate versus the number () of smoothing iterations for three values of the fine-grid spacing .

The above examples are for two grids. When more than two grids are used, the smoothing steps are divided among smoothings before () and after () each CGC. We have found can impair convergence if many coarse grids are used, while can lead to a bad behaviour in the first iterations. The best choice is to use and, if , then to make it after the prolongation (i.e. and ). In what follows, when we say that we will be actually indicating that .

3.3. The influence of the number of coarse grids

Finally, the convergence rate also depends on the number of coarse grids used. In Fig. 11a we show the variation of the convergence error with the iteration number for multigrid V-cycle iterations, for =2 km and using two, three or more grids. Fig. 11b shows the variation of with for a case with km. Note also that the sensitivity of to for a given finest grid resolution level depends on the number of coarse grids, i.e. it increases when we use more coarse grids. Note that when , the convergence speed depends much more strongly on the number of grids used than on .

Fig. 11. a The convergence error of the MG method using 2, 3, 4 and 5 grids ( =2 km and =2) b The convergence rate versus the number of smoothing iterations for three choices of the number of grids, but using always =7.5 km.

Finally, it is worth mentioning that the multigrid convergence rate is slightly better for W-cycles than for V-cycles when one uses a large number of coarse grids. However, performing W-cycles requires more computational work, and we have not found any significant improvement from the use of W-cycles instead of V-cycles.

© European Southern Observatory (ESO) 1997

Online publication: May 26, 1998

helpdesk.link@springer.de