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

2. The non-linear multigrid method

The aim of this section is to describe in detail the standard version of the non-linear multigrid method. To this end we, first, formulate in Sect. 2.1 the multilevel transfer problem pointing out the basic features of two "classical" iterative schemes which have been developed for solving this problem: one called MALI (Rybicki & Hummer, 1991, 1992; see also Paper I) which is based on Jacobi iterations, and other called MUGA (cf. TF-1; TF-2) which is based on Gauss-Seidel iterations. We then study in Sect. 2.2 the smoothing properties of these two iterative methods, demonstrating that the method of choice for the smoothing part of a multigrid RT code is the GS-based method of TF-2. Sect. 2.3 derives the equation which is at the basis of the multigrid method: the coarse-grid equation. The standard multigrid method itself is considered in Sect. 2.4, while Sect. 2.5 describes a good stopping criterion for deciding when the standard multigrid iterative process can be terminated.

2.1. The multilevel transfer problem

The multilevel non-LTE transfer problem is the simultaneous solution of the transfer equation for the radiation field and the rate and conservation equations for the level populations (cf. Mihalas, 1978 and Paper I). Because the opacities and emissivities depend on the populations, which, in turn, depend on the radiative rates, the problem is both strongly non-linear and non-local.

The first step in its solution is the discretization of the spatial dependence. In fact, in this paper we use a set of grids, whose spatial resolution is indicated by the level index, l, and the convention that the larger the positive integer number l the finer the grid. We replace the continuous variation of quantities by a discrete set of values at NP_l grid points, and all equations by their discrete approximations.

There are two sets of equations in the resultant system: those for the radiation field, and those for the populations. The population equations are deceptively simple in form,

where is a block-diagonal matrix formed by NP_l sub-matrices, each NL NL in size. NL is the number of atomic levels being treated in the vector , which like the known vector is of length NL NP_l. The coefficients in Eq.(  1) depend on the collision rates and thermodynamic variables, which are assumed to be known a priori, and the radiative rates, whose self-consistent values are being sought. Because the operator of Eq. (1) is block -diagonal it would appear that populations at each point are independent. This, of course, is fundamentally incorrect. The values at all points in the grid are coupled non-linearly by the radiation field. Because of this inherent non-linearity, the solution of the multilevel non-LTE problem requires an iterative method capable of finding the populations such that Eq. (1) is satisfied when the radiative rates, which appear in the block -diagonal matrix , are calculated from those populations via the solution of the RT equation.

The basic difference among the various strategies that have been proposed lies in the way one constructs, at each iterative step, a linear set of equations whose solution leads to correction of the current estimates. The simplest procedure one might think of is iteration: Using the current estimate , evaluate the opacities and source functions, solve the transfer equation and compute the radiation field in all transitions; then, with the radiative rates obtained, the resulting linear system would be

where is a NP_l NP_l block-diagonal matrix. Unfortunately, as is well-known (cf. Mihalas, 1978), this simple iteration scheme has very poor convergence properties, and is useless for solving optically thick non-LTE problems.

A successful multilevel iterative scheme for the self-consistent solution of Eqs. (1) is the one we applied in Paper I. That method is based on the preconditioning strategy of Rybicki & Hummer (1991, 1992), on a local approximate operator given by the diagonal of the full operator, and on the short-characteristics formal solution technique (cf. Kunasz & Auer, 1988; Auer & Paletou, 1994; Paper I). In this method, the linear system one solves in order to obtain the "improved" estimate of the atomic level populations is

where like is a block-diagonal matrix whose elements are obtained via the formal solutions of the transfer equation using opacities and source functions calculated directly from the population numbers of the previous iteration. This particular multilevel accelerated iteration scheme (Rybicki & Hummer 1991; 1992; see also Paper I) may be considered a generalization to the non-linear multilevel atom case of the Jacobi-based method which OAB developed for the linear two-level atom case. As we shall show below the smoothing capabilities of this multilevel Jacobi scheme (hereafter "the MALI scheme") are not sufficient to produce a powerful multigrid RT method.

A superior multilevel iterative scheme was developed by TF-2, and may be considered a generalization to the non-linear multilevel atom case of the Gauss-Seidel RT method which TF-1 presented for the linear two-level atom case. At each iterative step the linear system one has to solve to obtain a "new" estimate of the atomic level populations is as simple as above:

since is also a block-diagonal matrix, but where the elements of the block -corresponding to the spatial grid point j - are obtained via formal solutions using opacities and source functions calculated from the "new" population numbers (already available at the points , , ..., ) and from the "old" populations associated to the remaining points for which the corrections have not yet been computed (see TF-1 and TF-2 for details). As we shall illustrate below, the smoothing capabilities of this multilevel Gauss-Seidel method (hereafter "the MUGA scheme") are very good and yield a powerful multigrid RT method.

We point out that, in the three methods summarized above, the calculation at the current iterative step of the estimate, , requires only the inversion of NP_l independent blocks, i.e. one point after the other. The computing time per iteration is indeed virtually the same for these three methods, but the number of iterations required to reach convergence is at least a factor 2 larger for MALI than for MUGA (see TF-2). Therefore, since the MUGA scheme of TF-2 is faster than the MALI method of Paper I, we shall always compare the performance of the non-linear multigrid RT method developed in this paper with that of the MUGA scheme.

Before examining the smoothing properties of the MALI and MUGA methods we should mention that our formal solvers for 1D, 2D and 3D multilevel transfer applications are based on the short-characteristics (SC) technique (cf. Kunasz & Auer, 1988; Auer & Paletou, 1994; Paper I). The TF-1 and TF-2 papers show the basic features of the formal solution solvers that we had to develop for performing the GS-based MUGA iterations. Our multidimensional formal solvers use periodic boundary conditions, which allow us to treat plasma structures that repeat themselves periodically in the horizontal direction. In this paper we shall show examples of 1D and 2D multilevel calculations with the aim of illustrating the multigrid performance. We shall leave the topic of 3D multilevel transfer for a future publication.

2.2. The smoothing ability of the MALI and MUGA schemes

As with other operator splitting techniques, the convergence rate of the MALI and MUGA methods deteriorates as the resolution level l of the grid is increased; i.e., the spectral radius of the amplification matrix for the scheme tends to unity as the grid size is decreased (see Paper I, TF-1, and TF-2). What actually happens in fine grids is that the amplitude of the low-frequency Fourier spatial-components of the error are only slightly reduced in each iteration, despite the very effective reduction of the amplitude of the high-frequency components.

In order to illustrate this behaviour we shall now show some results of multilevel calculations performed with the MALI and MUGA schemes. We use the same standard 5-level Ca II atomic model and the same 1D atmospheric model described in Paper I. The initialization of the atomic level populations in a given grid of level l was a rapidly-fluctuating function that we created by applying to the LTE population levels a sinusoidal fluctuation with a wavelength of four grid points. This was done in order to simulate an initial error characterized by high spatial-frequency components. The solid line of Fig. 1 shows, for the fourth level of Ca II, the error in the departure coefficient for this initialization, and the dashed line shows the corresponding low-frequency error. That low-frequency component of the error, , is calculated by applying to the total error a spatial smoothing filter . Likewise, at each iterative step "itr ", we find the high-frequency error component by

where

is the full error of the current population numbers with respect to the fully converged solution.

Fig. 1. The solid line gives the total error (Eq. 6) in the departure coefficient of the fourth atomic level of Ca II corresponding to our highly-fluctuating initialization. The dashed-line shows the low-frequency error component. Grid =20 km.

In order to study the convergence properties of all these iterative methods we will use the same quantities introduced in Paper I: the relative change , the relative convergence error , and the relative true error . For example, the relative convergence error is defined as

where is the norm, and the expression " " is to be understood as the vector whose j -component is equal to the j -component of vector divided by the j -component of the population vector . For instance, the expression for the convergence error used in Paper I is nothing but Eq. (7) with , since the norm is defined as the maximum absolute value of such vector components. Thus, in Paper I, our choices for , and were the -norm of the bracketed quantities there. However, one is free to make a study of the convergence properties of an iterative method by choosing a different norm, like e.g. the Euclidean norm, which is also called the 2-norm. The 2-norm of a general vector of dimension D is given by

Note that, in our multilevel RT context, the dimension D=NP NL. The 2-norm seems to be a more standard choice among mathematicians, and we have used it throughout the main body of this paper for investigating the mathematical properties of our non-linear multigrid RT methods. We point out, however, that all the conclusions of this paper remained basically the same when using the -norm instead of the 2-norm.

Fig. 2 shows the convergence error corresponding to both the full error and to the high-frequency error component . First, note that the MUGA scheme of TF-2 has, in general, better convergence properties than the MALI scheme of Paper I. Note also that while both methods are very efficient in reducing the high-frequency error components in the fine grid, only the MUGA scheme also has this behaviour on the coarse grid. The number of iterations one has to perform with MALI to reduce the high-frequency error components is generally larger than with MUGA.

Fig. 2. The variation with the iteration number of the total convergence error (cf. Eq. 6) and of the high-frequency component of the error (cf. Eq. 5). The solid lines refer to a 1D grid with km, while the dotted ones to km. The results of a where obtained with the MALI method of Paper I, while those of b with the MUGA method of TF-2.

A more appropriate demonstration of the smoothing ability of these two multilevel schemes is given in Fig. 3. This figure shows, for three grids of different resolution levels, the variation with the iteration number of a smoothing number () which quantifies the smoothness of the error vector (Hackbush, 1985). This smoothness is determined by the relative size of the total error and its high-frequency component. Our choice for the smoothing number is

where and , i.e. the symbol means that smoothing iterations have been applied to the initialization using either the MALI or the MUGA schemes.

Fig. 3. The variation of the smoothing number against the number () of smoothing iterations: a for the MALI scheme and b for the MUGA method. Solid lines refer to km, dotted lines to  km, while dashed-lines to  km.

As indicated by Eq. (9), the operator is the 2-norm of the second-order spatial derivative. The smoothing number given by Eq. (9) thus provides a measure of the smoothness of the error vector after having carried out iterations with the MALI or MUGA schemes. No smoothing (e.g. for ) is indicated by =1, while very low values of imply a high degree of smoothing. Therefore, Fig. 3 shows that the smoothing capabilities of the MALI scheme drastically deteriorate when going from fine to coarse grids, while the MUGA scheme of TF-2 does indeed perform an excellent smoothing job for all the grid resolution levels.

Having compared the smoothing capabilities of these two methods, we conclude that the MUGA scheme (cf. TF-2) is the method of choice for the required smoothing iterations in the multigrid non-LTE method.

2.3. The coarse-grid equation

The above presentation was aimed not only to compare the smoothing capabilities of the MALI and MUGA schemes, but also to emphasize that the coarser the grid the faster the convergence of the low-frequency components of the error. Multigrid methods are based precisely on this last observation. One seeks a coarse-grid equation whose solution permits the calculation of a coarse-grid correction which, once it is interpolated to the fine grid, provides the fine-grid correction to the current fine-grid estimate. By doing this one aims at improving the convergence of the low-frequency components of the fine-grid error.

Suppose one has a fine-grid estimate such that its residual

is smooth. (We have used this particular notation in order to stress that the calculation of the residual just requires the evaluation of the same iteration block -diagonal matrix as Eq. 2). One would like to obtain a fine-grid correction such that the new estimate

satisfies Eq. (1), i.e. such that

Since the current residual is given by Eq. (10) we also have that

The crucial point is the following: Since the residual is assumed to be smooth, we can map the left-hand side of Eq. (13) to a coarser grid of level . This leads directly to the following coarse-grid equation:

where the linear operator is a fine-to-coarse or restriction operator (we point out that if is a fine-grid vector having fine-grid accuracy, then is a coarse-grid vector whose values still have such fine-grid accuracy).

Note that the rhs of the system of Eqs. (14) can be obtained directly and that, therefore, Eqs. (14) are formally identical to the original system of Eqs. (1), but formulated for a grid of level . Once one has solved this coarse-grid equation to obtain (e.g. by using the fast MUGA scheme of TF-2 or any other multilevel method), the coarse-grid correction (CGC) is simply given by

and

where is a coarse-to-fine or prolongation operator (we point out that if is a coarse-grid vector having the accuracy provided by a given coarse-grid equation, then is a fine-grid vector whose values still have the accuracy provided by such a coarse-grid equation). We use cubic centered interpolation for the prolongation and a restriction given by the adjoint of the linear interpolation (see details in Hackbush, 1985). At the upper and lower boundaries we simply use for the trivial injection along the vertical direction, while we take the adjoint of the linear interpolation along the horizontal direction (cf. Hackbush, 1985). We have found optimal behaviour using these choices.

Eq. (14) is the desired coarse-grid equation (Brandt, 1977; see also Hackbush, 1985). It is crucial to note that one is solving this equation for , but that this solution for the populations in the coarse grid does not have the accuracy of the coarse-grid solution , which would be obtained by solving Eq. (1) but in a grid of level . What accuracy then is the coarse-grid Eq. (14) for the population numbers giving us? To answer this question we note again that the residual is given by Eq.  (10) and, thus, rewritten Eq.  (14) as follows

where

As pointed out nicely by Press et. al. (1994) is an approximation to the truncation residual defined in the coarse -grid relative to the fine grid, since the exact coarse-grid truncation residual would be just that given by Eq. (18) but using the fully converged solution instead of the current estimate . Therefore, in Eq. (17) one can think of as the correction to that "forces" the solution of the coarse-grid equation to have the accuracy of the fine-grid solution.

Fig. 4 aims at illustrating the efficiency of one CGC for an example where the fine grid spacing km and the coarse one is =120 km. Fig. 4a shows the error in the departure coefficient associated with an LTE initialization for . Fig. 4b gives the error corresponding to the "new" estimate obtained by means of one CGC (cf. Eq.   16). Note that only one CGC strongly reduces the total error of the initial estimate, but that the new estimate still has a high-frequency component that is not effectively removed by only a coarse-grid correction.

Fig. 4. The error in the departure coefficient before a and after b a pure CGC (cf. Eq. 16). The dashed-line corresponds to the Ca II ground level, the dotted line to the second level, and the solid line to the fourth one. The error has been calculated with respect to the fully converged solution in the fine grid which has km. The coarse-grid spacing chosen was km.

A further illustration of the role played by the CGC is given in Fig. 5. Here we show the height variation of the error of the departure coefficient in the fourth Ca II atomic level after one CGC, but for various two-grid combinations. Fig. 5a shows CGC examples for cases where , and we use various fine-grid spacings; note that the smaller the grid-spacing of the fine grid the higher the CGC (smaller the remaining error). Fig. 5b shows examples for a fixed fine -grid spacing but different coarse-grid spacings; note that the larger the grid spacing of the coarse grid the smaller the CGC (the larger the remaining error). By comparing these two figures one can see that it is the coarse grid resolution level that determines the low-frequency error component remaining after one CGC.

Fig. 5. The error in the departure coefficient of the fourth level of Ca II after a pure CGC (cf. Eq. 16). a For cases where the coarse-grid , with a fine-grid of 15 km (solid line), of 30 km (dotted line) and of 60 km (solid line with squares). b For a fixed fine-grid spacing of 15 km, but with coarse-grid equal to 30 km (solid line), 60 km (dotted line) and 120 km (solid line with squares).

The above examples show that the CGC is indeed very efficient in reducing the amplitude of the low-frequency components of the error. On the contrary, as is seen in Figs. 4 and 5, components of the error with wavelengths smaller than or similar to twice the distance between the coarse grid points remain, because such high-frequency components are not resolved by the coarse grid. For this reason the CGC, by itself, is a non-convergent iteration (see Hackbush, 1985 for a formal proof of this observation). What is needed to achieve a true two-grid convergent iterative scheme is to apply a number of suitable iterations in the fine grid to remove the high-frequency components of the error. As advanced earlier the MUGA scheme is the multilevel method of choice for this purpose. We note that, besides being very efficient in reducing the amplitude of the high-frequency error components, it also makes a contribution to the reduction of the low-frequency error components. Thus, the convergence rate of the non-linear two-grid iteration is not determined by the CGC alone. As we shall show below, it is actually the combination of smoothing iterations in the fine grid and the CGC that sets the very high convergence rate which is characteristic of the two-grid method.

2.4. The standard multigrid method

We may now summarize the steps of our non-linear two-grid method for multilevel RT applications as follows:

1. Pre-smoothing: Given the current estimate, perform smoothing iterations in the grid l using our MUGA method in order to obtain .
2. Coarse-grid correction step: Obtain according to Eq. (16). This is done by the following operations:

   - Compute the residual on the fine grid from Eq. (10). (Note that this requires formal solutions of the RT equation in the fine grid of level l in order to find the radiation field corresponding to the populations ).

   - Apply the restriction operator to the fine-grid residual to obtain .

   - Apply the restriction operator to the current estimate to obtain .

   - Compute the first term in the rhs of Eq. (14). (Note that this requires formal solutions of the RT equation on the coarse grid in order to calculate the radiation field corresponding to the populations ).

   - Use the MUGA method to solve the coarse-grid Eq. (14), and then obtain the correction according to Eq. (15).

   - Apply the prolongation operator to this coarse-grid correction in order to obtain the fine-grid correction and a new estimate as indicated by Eq. (16). (It is very important to note that, as the prolongation to the fine grid of the coarse-grid correction given by Eq. (15) only provides an approximate correction, one does not actually need to solve the coarse-grid Eq. (14) exactly. As we shall emphasize below, it is sufficient to iterate using the MUGA method only till achieving a reduction of an order of magnitude in the error of the initial estimate used for the solution of Eq. (14)).

3. Post-smoothing: Perform smoothing iterations in the grid l using the MUGA scheme. Terminate the multigrid iterative process once a rigorous stopping criterion is satisfied (see Sect. 2.5); otherwise return to point (1).

These steps define a two-grid (TG) cycle. In the non-linear problem, one is solving the coarse-grid equation for , and not just for the correction as in the linear case (cf. Hackbush, 1985; Steiner, 1991). Further, in the non-linear case, the restriction operator has to be applied not only to the residual , but also to the current estimate . Besides the additional complexity of having to develop a suitable non-linear multilevel scheme (see TF-2) for the smoothing part and for solving rapidly the coarse-grid equation, these are the main differences between a linear and non-linear TG cycle.

A three-grid method is obtained if the coarse-grid Eq. (14) is solved by applying a number () of two-grid iterations involving grids with resolution levels and . A multigrid (MG) method is obtained if one applies this idea recursively down to some coarsest grid where the solution can be found easily by using any of the multilevel methods currently in use. Fig. 6 gives the usual pictorial representation of a multigrid cycle for three and four grids and for two values of .

Fig. 6. Schematic visualization of the standard multigrid iterative scheme for some cases: a two grids, b three grids with , i.e. the V-cycle, c three grids with , i.e. the W-cycle. The symbol indicates smoothing, restriction, and prolongation. CGE means "coarse-grid equation".

Concerning the resolutions of the spatial grids, we have found that an excellent choice to get the successively coarser grids is simply to double the vertical () and horizontal ( and ) step sizes, i.e. halve the number of grid-points in each direction. This implies that, in 1D, the coarse-grid reduction factor is , in 2D , and in 3D . As we shall see in more detail below, with the TG method the computational effort required to solve the CGE increases as the spatial resolution of the fine-grid improves; however, the MG method does not suffer from this limitation because as the fine-grid resolution level "l " increases we correspondingly increase the number (N) of coarse grids, so that the CGE is always solved in the same coarsest grid.

Before studying in detail the convergence rate of the multigrid RT code it is instructive to show an example of its performance. Fig. 7 gives the variation with the iteration number of the true error (), of the convergence error (), and of the relative change () corresponding to the same 5-level Ca II two-dimensional model problem of Paper I, which is characterized by sinusoidal temperature fluctuations along the horizontal direction with an amplitude of 500 K and a horizontal wavelength of 750 km. First, note that our non-linear multigrid method for multilevel RT applications gives the converged solution (i.e. a -value smaller than the truncation error ) in only three iterations. Second, note that the relative changes are smaller than the convergence error . This last feature can be easily understood after recalling, from the appendix of our Paper I, that these quantities are related asymptotically by

where is given by Eq. (22) below. In Fig. 7 because the multigrid -values are well below 0.5. This is important because other methods currently in use (e.g. with MALI) have . With them, a small value of (which is all that one has available from the iterations themselves) does not necessarily imply a small value of (which is the quantity that has to be sufficiently small to guarantee that convergence has been achieved). The convergence rate of our multigrid RT method, however, is so high that a small value of directly implies an even smaller value of .

Fig. 7. Convergence properties of the multigrid RT method are demonstrated in this 2D Ca II calculation with a horizontal periodicity of 750 km in the temperature inhomogeneities.

2.5. A stopping criterion for the standard MG method

We have not yet discussed when the standard multigrid process should be terminated. As mentioned in Sect. 2.4 the check for convergence should be made after a number () of post-smoothing iterations in the finest grid. In Paper I we emphasized that one should actually terminate the iterations once the convergence error is dominated by the truncation error of the finest-grid selected. A suitable stopping criterion to achieve this goal within the framework of the standard multigrid method consists in terminating the iterative process once the -norm of the current fine-grid residual is smaller than the same norm of the fine-grid truncation residual, i.e. to stop iterating once

The relevant question now is: how can we estimate the fine-grid truncation residual ? Eq. (18) allows one to estimate the truncation residual () corresponding to the coarser grid of level " ", but not since one does not know , simply because the finest grid-level is "l " and not " " To estimate the fine-grid residual we follow Press et al. (1994) and note that for a solution method like ours (which has second-order accuracy and which uses a coarse-grid spacing twice larger than the fine-grid one) one has

Fig. 8 shows this stopping criterion working in practice. The figures show the variation of the 2-norm of the fine-grid residuals versus the iteration number for two cases: a finest grid with (a) km and (b) km. The solid lines give the estimate of the finest-grid truncation residual () at each iteration. The dashed-lines give the variation of the finest grid residual () (cf. Eq. 10). By comparing the truncation residual values of Fig. 8a and Fig. 8b one can see that the relation given by Eq. (21) is satisfied. The asymptotic value for is rapidly reached, i.e. the values for from Eq. (18) do not significanlty change after the first iteration. This demonstrates that this stopping criterion is easily applied, and that only 2 standard multigrid iterations suffice to reach the true accuracy the chosen grids can provide.

Fig. 8. Illustration of a stopping criterion for the standard multigrid RT method working in practice.

© European Southern Observatory (ESO) 1997

Online publication: May 26, 1998

helpdesk.link@springer.de