<!-- metadata commented in wiki content

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Linear systems are obtained with discretization of the mathematical model, which consists in approximating, through algebraic equations, each term of the mathematical model for each grid node or point. This process leads to an algebraic equation system of the form

In CFD, the methods traditionally employed in this process are: Finite Difference Method (FDM) [2], Finite Volume Method (FVM) [3] and Finite Element Method (FEM) [4].

The algebraic equation system given by Eq. (1) can be solved using direct or iterative methods. In this work, iterative methods were employed due to the aforementioned characteristics of linear systems in CFD (sparse and large coefficients matrices), for which iterative methods are recommended. The multigrid method is one of the most effective methods to accelerate the convergence of iterative methods for the resolution of linear or nonlinear systems, isotropic or anisotropic problems, among others [5-7].

Anisotropic problems are fairly common in Engineering and appear in many phenomena, such as in the case of a material with different heat conduction behaviors for different directions. In this case, the coefficients of the differential equations are distinct among themselves and generate, what is called, physical anisotropy. Anisotropies can also appear from discretization of grids with different spacing in each direction, for instance, boundary layer problems. This is called geometric anisotropy [5,6]. The efficiency of the multigrid method has not yet been fully achieved for problems with strong anisotropy, either physical or geometric [8].

Physical anisotropy problems have been investigated by Rabi and de Lemos [9], who discretized the two-dimensional advection-diffusion equation combining null and constant coefficients. Finite volume method was used in the discretization of the equations. Multigrid method was employed using correction scheme, Gauss-Seidel solver and V- and W-cycles. The authors presented a study of the different speed ranges (null and constant), number of grids, number of smoothing steps at each grid level and different solvers. They concluded that there was a significant reduction in the computational effort when the speed range values were increased.

Wienands and Joppich [10] presented an in-depth study on the Local Fourier Analysis (LFA) and its application on several problems, which included anisotropic problems. The authors calculated the convergence factor of the multigrid method for the anisotropic diffusion equation with different solvers and restriction and prolongation operators.

Johannsen [11] solved an anisotropic diffusion problem using finite volume method for discretizing the equations and 9-point incomplete LU (ILU) decomposition method for solving the linear equations systems. The author employed LFA to demonstrate the superior smoothing properties of ILU.

Oliveira et al. [8] assessed geometric anisotropy for different grids and aspect ratios. They also assessed some components of the multigrid method, such as: solvers, type of restriction, number of levels and number of inner iterations, among several coarsening algorithms. They concluded that Partial Weighting (PW) had a good performance.

Vinogradova and Krukier [12] solved a three-dimensional advection-diffusion problem with intermediate anisotropy using FDM for the discretization of the equations and ILU for the resolution of the linear equation systems. They concluded that the proposed methodology is efficient, but it has the disadvantage of having limitations in the coefficients of the mixed derivatives, which has no physical meaning.

Vassoler-Rutz et al. [11] analyzed the effect of physical anisotropy on multigrid method for two anisotropic diffusion problems. They used FAS scheme, V-cycle, and Modified Strongly Implicit (MSI) and Gauss-Seidel (GS) solvers. They concluded that, for strong anisotropies, the complexity order of the multigrid method is not suitable.

Several works on the implementation of the multigrid method found in the literature demonstrate that the choice of the multigrid components is crucial for the convergence or not of the method. Trottenberg et al. [6] state that these choices are difficult and thus small changes can considerably improve convergence. In this sense, LFA can assist these choices as it allows to predict the performance of the multigrid method, since it provides estimates of the converge rates based on the variation of the multigrid method components.

Pinto et al. [14] solved the anisotropic diffusion problem using ILU in triangular grids. They used LFA to show the good smoothing properties of the solver and the asymptotic convergence of the multigrid.

Franco et al. [13] performed LFA in transient problems and obtained the critical value of the parameter that represents the level of space-time anisotropy for the 1D and 2D Fourier equations.

In this work, an efficient and robust method for solving physical anisotropy problems using LFA is proposed. A two-dimensional diffusion mathematical model is considered, in which physical anisotropy appears in the coefficients and it will be denominated diffusion anisotropy. Equations were discretized using FDM with second-order central difference scheme.

</math>) of the multigrid method was calculated through assessment of the ILU solver in different directions [7] and several restriction and prolongation operators. The results obtained by means of LFA were used to assess the influence of physical anisotropy on computational cost by means of CPU time and number of operations in each V-cycle and at the restriction step.

The remainder of this work is organized as follows: section 2 presents the mathematical and numerical models. Section 3 discusses considerations regarding the LFA used. Section 4 presents the results of the convergence analysis and complexity analysis. Section 5 presents the conclusion.

The diffusion anisotropy problem will be assessed through the two-dimension diffusion equation given by Eq. (2) [5,6]

| <math>\begin{cases} \varepsilon T_{xx}-T_{yy}=S \\ T(0,y)=T(x,0)=T(x,1)=T(1,y)=0 \end{cases}

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(3)

 

Eq. (2) was discretized using FDM with CDS, resulting in

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(4)

where <math>T</math> is the system unknown.

Figure 1(b) depicts the notation of the grid points in Fig. 1(a). The points P (central), W (west), E (east), N (north) and S (south) in Fig. 1(b) correspond to the points <math display="inline">(i,j),(i-1,j),(i+1,j),(i,j+1),(i,j-1)</math> in Fig. 1(a), respectively.               

|

|Figure 1: Points of a uniform two-dimensional grid.  

The discretization of Eq. (2) results in Eq. (4), and for the inner points, considering <math display="inline">h_{x}^{{}}=\frac{1}{N_{x}^{{}}-1}</math> and <math display="inline">h_{y}^{{}}=\frac{1}{N_{y}^{{}}-1}</math>

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;" |(5)

===2.2. Multigrid method and computational details===

The multigrid method accelerates the convergence rate of iterative methods. It consists in employing a group of grids with different refinement levels. At each grid refinement level, the more oscillatory errors are smoothed, and only low frequency errors remain. After passing to another grid, the remaining low frequency errors become more oscillatory. The efficiency of this process, called smoothing, depends on the choice of a suitable solver.

For employing multigrid, besides a solver with good smoothing properties, grid transfer operators are required (restriction and prolongation).

In [8] and [16], restriction through partial weighting in the directions <math>x</math> and <math>y</math>, henceforth denoted by <math display="inline">{\mbox{PW}}_\mbox{x}</math> and <math display="inline">{\mbox{PW}}_\mbox{y},</math> respectively, applied in problems involving geometric anisotropy was proposed. These operators, are given in stencil notation as

| <math>\text{P}{{\text{W}}_{\text{x}}}</math> : <math display="inline">I_{h}^{2h}=\frac{1}{4}\left( \begin{matrix}

\end{matrix} \right)

</math>, <math>\text{P}{{\text{W}}_{\text{y}}}</math> : <math>I_{h}^{2h}=\frac{1}{4}\left( \begin{matrix}

\end{matrix} \right)</math>.

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(6)

In this work, such restriction was combined with 7-point incomplete LU decomposition (henceforth denoted by <math>\mbox{ILU}</math>). According to [17], this decomposition has a better convergence factor than 5-point incomplete LU decomposition for anisotropic problems.

In Eq. (2), discretized using FDM, the stencil for 5-point Laplacian operator is given by

| <math>{{L}_{h}}={{\left( \begin{matrix}

\end{matrix} \right)}_{h}}

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(7)

The <math>\mbox{ILU}</math> decomposition of this same operator will be given by

| <math>{{L}_{h}}={{\left( \begin{matrix}

\end{matrix} \right)}_{h}}

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(8)

| <math>{{\overset{{}}{\mathop{L}}\,}_{h}}={{\overset{\hat{\ }}{\mathop{L}}\,}_{h}}{{\overset{\hat{\ }}{\mathop{U}}\,}_{h}}-{{R}_{h}}</math>,

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(9)

where <math>{{\overset{\hat{\ }}{\mathop{L}}\,}_{h}}</math>  is a lower triangular matrix,   <math>{{\overset{\hat{\ }}{\mathop{U}}\,}_{h}}</math> is an upper triangular matrix and  <math>{{R}_{h}}</math> is the residual matrix.

<math>{{\overset{\hat{\ }}{\mathop{L}}\,}_{h}}{{y}^{m}}={{r}^{m}}\,</math>,

<math>{{\overset{\hat{\ }}{\mathop{U}}\,}_{h}}\,{{\sigma }^{m}}={{y}^{m}}</math>,

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(10)

Depending on the ordination of the grid points, different directions can be obtained for the <math>\mbox{ILU}</math> decomposition. In lexicographical order,  <math display="inline">{\mbox{ILU}}_{\mbox{EN}}</math> [17], is given by

| <math>{{\overset{\hat{\ }}{\mathop{L}}\,}_{h}}={{\left( \begin{matrix}

\end{matrix} \right)}_{h}}, {{\overset{\hat{\ }}{\mathop{U}}\,}_{h}}={{\left( \begin{matrix}

\end{matrix} \right)}_{h}}, {{R}_{h}}={{\left( \begin{matrix}

\end{matrix} \right)}_{h}}

 

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(11)

Another example of ordination for <math>\mbox{ILU}</math>,  <math display="inline">{\mbox{ILU}}_{\mbox{NE}}</math> [17], is given by

<math>{{\overset{\hat{\ }}{\mathop{L}}\,}_{h}}={{\left( \begin{matrix}

\end{matrix} \right)}_{h}}, {{\overset{\hat{\ }}{\mathop{U}}\,}_{h}}={{\left( \begin{matrix}

\end{matrix} \right)}_{h}}, {{R}_{h}}={{\left( \begin{matrix}

\end{matrix} \right)}_{h}}

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(12)

The linear equation system given by Eq. (1) was solved using the geometric multigrid method [5,6] with correction scheme (CS), V-cycle and null initial guess.

The coarsening ratio is given by <math>r=2</math> (standard coarsening) [17]. The grid transfer operators employed were: Injection Restriction (INJ), Half Weighting (HW), Full Weighting (<math>\mbox{FW}</math>) (see [6]), Partial Weighting in <math display="inline">x</math> (<math display="inline">{\mbox{PW}}_\mbox{x}</math> ), Partial Weighting in <math display="inline">y</math> (<math display="inline">{\mbox{PW}}_\mbox{y}</math>) and prolongation by bilinear interpolation and 7-point interpolation. The equation systems obtained by means of discretization were resolved using 7-point <math>\mbox{ILU}</math> solvers in different directions (<math display="inline">{\mbox{ILU}}_{\mbox{EN}}</math>, <math display="inline">{\mbox{ILU}}_{\mbox{NE}}</math>, among others).

The stop criterion used to interrupt the iterative process is based on the non-dimensional residual norm. The residual of the algebraic equation system is defined by

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;" |(13)

Considering  <math>{{L}^{m}}={{\left\| r_{{}}^{m} \right\|}_{1}}</math> and  <math>{{L}^{0}}={{\left\| r_{{}}^{0} \right\|}_{1}}</math> , if  <math>\frac{{{L}^{m}}}{{{L}^{0}}}\le tol</math> the iterative process is interrupted if  <math>tol={{10}^{-10}}</math> .

== 3. Local Fourier Analysis ==

In order to perform the LFA, general discrete linear operators with constant coefficients are considered, which are defined in an infinite grid <math>G_h</math> , where the influence of the boundaries can be dismissed [6].

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(14)

For  <math>-\pi \le \theta <\pi </math> , every function of the grid  <math>{{\phi }_{h}}\left( \theta ,x \right)</math> are eigenfunctions of a discrete operator that can be written by a stencil.

| <math>{{L}_{h}}\,{{\phi }_{h}}\left( \theta ,x \right)=\overset{\tilde{\ }}{\mathop{{{L}_{h}}(}}\,\,\theta )\,{{\phi }_{h}}\left( \theta ,x \right)</math>,

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(15)

| <math>{{L}_{h}}\,(\theta )={{\left[ {{s}_{k}} \right]}_{h}}, \overset{\tilde{\ }}{\mathop{{{L}_{h}}}}\,\,(\theta )=\sum\limits_{k}{{{s}_{k}}{{e}^{i\,\theta \,k}}}</math> and <math display="inline">{s}_{k}</math> is the stencil notation of the operator.

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;" |(16)

For the smoothing and the analysis of two grids, it necessary to distinguish components of high and low frequency of  <math>G_h</math> in relation to  <math>G_{2h}</math> .

It is known that [6] only if

|  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(17)

<math>\varphi</math> is a low-frequency component<math>\Leftrightarrow \theta \in {{T}^{low}}=\left[ -\frac{\pi }{2},\frac{\pi }{2} \right)\times \left[ -\frac{\pi }{2},\frac{\pi }{2} \right)</math>

<math>\varphi</math> is a high-frequency component<math>\Leftrightarrow \theta \in {{T}^{high}}=\left[ -\pi ,\pi  \right)\times \left[ -\pi ,\pi  \right)\backslash \left[ -\frac{\pi }{2},\frac{\pi }{2} \right)\times \left[ -\frac{\pi }{2},\frac{\pi }{2} \right)</math>. See Fig. 2.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">

 

<span id='_Ref428218644'></span><span id='_Toc428200463'></span><span id='_Toc428200508'></span><span id='_Toc429758843'></span><span id='_Ref466666326'></span>

{| class="formulaSCP" style="width: 100%;margin: 1em auto 0.1em auto;width: 100%;text-align: center;"

|  

{| style="text-align: center; margin:auto;width: 100%;"

|-

|Figure 2: Low- (inner white area) and high-frequency (hatched area) areas.

\end{align} \right.</math>.

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;" |(18)

The operator <math>K_{h}^{2h}</math> is represented by a 4x4 matrix  <math>\hat{K}_{h}^{2h}</math> , as follows

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;" |(19)

where  <math>\hat{I}_{h}^{{}}</math> is represented by a 4x4 identity matrix,  <math>{{\hat{L}}_{h}}(\theta )</math> is the 4x4 matrix, <math>\hat{I}_{h}^{2h}(\theta )</math>  is a 1x4 matrix,  <math>\hat{I}_{2h}^{h}(\theta )</math> is a 4x1 matrix and  <math>{{\left( {{{\hat{L}}}_{2h}}(2\theta ) \right)}^{-1}}</math> is a 1x1 matrix.

A representation for <math display="inline">M_{h}^{2h}</math> can be obtained by a matrix  <math>\hat{M}_{h}^{2h}(\theta )</math> of the form

| <math>\hat{M}_{h}^{2h}:={{({{\hat{S}}_{h}}(\theta ))}^{{{v}_{2}}}}\hat{K}_{h}^{2h}(\theta )\,{{({{\hat{S}}_{h}}(\theta ))}^{{{v}_{1}}}}</math>,

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;" |(20)

where <math>\hat{K}_{h}^{2h}(\theta )</math> is given by Eq. (19) and <math>{{\hat{S}}_{h}}(\theta )</math> is a 4x4 matrix and represents <math>{{S}_{h}}(\theta )</math>.

{| class="formulaSCP" style="width: 100%;margin: 1em auto 0.1em auto;width: 100%;text-align: center;"  

| <math>\Lambda =\left\{ \theta \in \left[ -\frac{\pi }{2},\frac{\pi }{2} \right)\times \left[ -\frac{\pi }{2},\frac{\pi }{2} \right):\,{{\overset{\tilde{\ }}{\mathop{L}}\,}_{h}}(\theta )=0\,\,\text{or}\,\,{{\overset{\tilde{\ }}{\mathop{L}}\,}_{2h}}(\theta )=0 \right\}</math>.

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(21)

The asymptotic convergence factor <math>\rho \left( M_{h}^{2h} \right)</math> can be calculated by

{| class="formulaSCP" style="width: 100%;margin: 1em auto 0.1em auto;width: 100%;text-align: center;"  

|<math>\rho \left( M_{h}^{2h} \right)=\sup \left\{ \rho \left( \hat{M}_{h}^{2h}(\theta ) \right):\,\,\theta \in {{T}^{low}},\,\,\theta \notin \Lambda \right\}</math>,

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(22)

where <math>\rho \left( \hat{M}_{h}^{2h}(\theta ) \right)</math> is the spectral radius of the 4x4 matrix <math>\hat{M}_{h}^{2h}(\theta )</math>.

 

In this work, LFA was used to determine the asymptotic convergence factor of the multigrid method <math>\bigl(\rho \left( M_{h}^{2h} \right)={{\rho }_{loc}}\bigr)</math> combining <math>\mbox{ILU}</math> solvers in several directions (such as  <math display="inline">{\mbox{ILU}}_{\mbox{EN}}</math> and  <math display="inline">{\mbox{ILU}}_{\mbox{NE}}</math>), <math>\mbox{FW}</math>, HW, INJ,  <math display="inline">{\mbox{PW}}_\mbox{x}</math> and  <math display="inline">{\mbox{PW}}_\mbox{y}</math> restriction operators and bilinear and 7-point prolongation operators.

 

For the <math>\mbox{FW}</math> restriction operator, <math>\overset{\tilde{\ }}{\mathop{I_{h}^{2h}}}\,\left( {{\theta }^{\alpha }} \right)=\frac{1}{4}(1+\cos {{\bar{\theta }}_{1}})(1+\cos {{\bar{\theta }}_{2}})</math>, for the <math display="inline">{\mbox{PW}}_\mbox{x}</math>, <math>\overset{\tilde{\ }}{\mathop{I_{h}^{2h}}}\,\left( {{\theta }^{\alpha }} \right)=\frac{1}{2}(1+\cos {{\bar{\theta }}_{1}})</math> and for the  <math display="inline">{\mbox{PW}}_\mbox{y}</math>, <math>\overset{\tilde{\ }}{\mathop{I_{h}^{2h}}}\,\left( {{\theta }^{\alpha }} \right)=\frac{1}{2}(1+\cos {{\bar{\theta }}_{2}})</math>. For the other restriction operators, see [4].

 

For the bilinear prolongation operator, <math>\overset{\tilde{\ }}{\mathop{I_{2h}^{h}}}\,\left( {{\theta }^{\alpha }} \right)=(1+\cos {{\bar{\theta }}_{1}})(1+\cos {{\bar{\theta }}_{2}})</math> and for the 7-point prolongation operator, <math>\overset{\tilde{\ }}{\mathop{I_{2h}^{h}}}\,\left( {{\theta }^{\alpha }} \right)=\left( 1+\cos {{{\bar{\theta }}}_{1}}+\cos {{{\bar{\theta }}}_{2}}+\cos ({{{\bar{\theta }}}_{1}}-{{{\bar{\theta }}}_{2}}) \right)</math> [10].

In order to perform the LFA using the  <math display="inline">\mbox{ILU}</math> solver, the eigenfunctions of <math>{{L}_{h}}</math>, <math>{{\overset{\hat{\ }}{\mathop{L}}\,}_{h}}</math>, <math>{{\overset{\hat{\ }}{\mathop{U}}\,}_{h}}</math> and <math>{{R}_{h}}</math> are given by  

| <math>{{\lambda }_{h}}(\theta ),\,\,\,\lambda _{h}^{L}(\theta ),\,\,\,\lambda _{h}^{U}(\theta )\,\,\text{e}\,\,\,\lambda _{h}^{R}(\theta )\,\,\,</math> with <math>-\pi \le \theta <\pi </math>.

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;" |(23)

The smoothing operator <math>{{S}_{h}}</math>, according to [6], is given by

| <math>{{S}_{h}}\phi (\theta ,x)={{\overset{\tilde{\ }}{\mathop{S}}\,}_{h}}\phi (\theta ,x)</math>, <math>-\pi \le \theta <\pi </math>,

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;" |(24)

{| class="formulaSCP" style="width: 100%;margin: 1em auto 0.1em auto;width: 100%;text-align: center;"  

|<math>{{\overset{\tilde{\ }}{\mathop{S}}\,}_{h}}(\theta ):=\frac{\lambda _{h}^{L}(\theta )\lambda _{h}^{U}(\theta )-\lambda (\theta )}{\lambda _{h}^{L}(\theta )\lambda _{h}^{U}(\theta )}=\frac{\lambda _{h}^{R}(\theta )}{{{\lambda }_{h}}(\theta )+\lambda _{h}^{R}(\theta )}</math>.

| style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(25)

For <math display="inline">{\mbox{ILU}}_{\mbox{EN}}</math>, <math>\lambda _{h}^{R}(\theta )\,={{p}_{1}}{{e}^{i(2{{\theta }_{1}}-{{\theta }_{2}})}}+{{p}_{3}}+{{p}_{2}}{{e}^{i(-2{{\theta }_{1}}+{{\theta }_{2}})}}</math> and for  <math display="inline">{\mbox{ILU}}_{\mbox{NE}}</math>, <math>\lambda _{h}^{R}(\theta )\,={{p}_{1}}{{e}^{i(-{{\theta }_{1}}+2{{\theta }_{2}})}}+{{p}_{3}}+{{p}_{2}}{{e}^{i({{\theta }_{1}}-2{{\theta }_{2}})}}.</math>

 

 

Equation (2) was assessed for <math>\varepsilon ={{10}^{\kappa }}</math>  and <math>\varepsilon ={{10}^{-\kappa }}</math>, with <math>\kappa \in \Kappa =\{0,\,\,1,\,\,2,\,\,3,\,\,4,\,\,5,\,\,6,\,\,7\}</math>. When <math>\varepsilon ={{10}^{\kappa }}</math> or <math>\varepsilon ={{10}^{-\kappa }}</math> in this work, there is symmetric anisotropy. For instance, <math>\varepsilon ={{10}^{2 }}</math> is an anisotropy symmetric to  <math>\varepsilon ={{10}^{-2}}</math>.

 

 

 

Figure 3 depicts <math>{{\rho }_{loc}}</math>, given by Eq. (22), with <math display="inline">\mbox{ILU}</math> in the EN, NE, ES, SE directions, <math>\mbox{FW}</math> restriction, bilinear prolongation, number of inner iterations <math>v=2</math>, <math>\varepsilon ={{10}^{\kappa }}</math> and  <math>\varepsilon ={{10}^{-\kappa }}</math>, with <math>\kappa \in K</math>.

 

|Figure 3: <math>{{\rho }_{loc}}</math> ''versus'' anisotropy coefficients <math>\bigl(\varepsilon\bigr)</math> with  <math display="inline">\mbox{ILU}</math> in different directions.

 

 

{| class="formulaSCP" style="width: 100%;margin: 1em auto 0.1em auto;width: 100%;text-align: center;"

|Figure 4: <math>{{\rho }_{loc}}</math> ''versus'' anisotropy coefficients <math>\bigl(\varepsilon\bigr)</math> with different interpolation operators.

It is observed that the restriction|prolongation combinations <math>\mbox{FW}</math>|bilinear and <math>\mbox{FW}</math>|7-points had a good performance <math>\bigl({{\rho }_{loc}}<<1\bigr)</math> and presented very similar convergence factors.

Bilinear prolongation operator was used in the following analysis as it is easy to program and demands fewer memory resources. The asymptotic convergence factors were compared with different restriction operators.

 

{| class="formulaSCP" style="width: 100%;margin: 1em auto 0.1em auto;width: 100%;text-align: center;"

|Figure 5: <math>{{\rho }_{loc}}</math> ''versus'' anisotropy coefficients <math>\bigl(\varepsilon\bigr)</math> with different restriction operators.

Figure 5 shows that for <math>\varepsilon ={{10}^{\kappa }}</math> and  <math>\varepsilon ={{10}^{-\kappa }}</math>, with <math>\kappa \in K</math> (symmetric anisotropies), <math>{{\rho }_{loc}}</math> presents very similar values. It is noted that for anisotropic problems <math>\bigl(\kappa\neq0\bigr)</math>, the lowest values for <math>{{\rho }_{loc}}</math> are achieved with <math>\mbox{FW}</math> and  <math display="inline">{\mbox{PW}}_\mbox{x}</math> restriction, which present very similar values.

Apply <math display="inline">{\mbox{ILU}}_{\mbox{NE}}</math> smoothing with '''REST '''restriction

else if <math>\varepsilon =1</math> then

Apply  <math display="inline">{\mbox{ILU}}_{\mbox{NE}}</math> smoothing with <math>\mbox{FW}</math> restriction

Apply  <math display="inline">{\mbox{ILU}}_{\mbox{EN}}</math> '''REST '''restriction

Next, it is presented the asymptotic convergence factor <math>{{\rho }_{loc}}</math>, calculated by LFA, and the empiric asymptotic convergence factor <math>\rho_h</math>, for different anisotropy coefficients.

Figure. 6 shows Algorithm 1 with '''REST''' <math display="inline">={\mbox{PW}}_\mbox{x}</math> ,<math>\nu=2</math> and bilinear prolongation.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">

[[Image:draft_Vassoler Rutz_344011008-image187.jpeg|420px]] </div>

{| class="formulaSCP" style="width: 100%;margin: 1em auto 0.1em auto;width: 100%;text-align: center;"

|  

{| style="text-align: center; margin:auto;width: 100%;"

|Figure 6: <math>{{\rho }_{loc}}</math> and <math>\rho_h</math> versus anisotropy coefficients <math>\bigl(\varepsilon\bigr)</math>.

Figure. 7 depicts the numerical asymptotic convergence factor <math>{{\rho }_{loc}}</math> calculated by LFA and the experimental asymptotic convergence factor <math>\rho_h</math>, for different anisotropy coefficients for different grids. Algorithm 1 with  '''REST''' = <math display="inline">{\mbox{PW}}_\mbox{x}</math> , <math>\nu=2</math> and bilinear prolongation was used. As the grid  becomes more refined, <math>\rho_{h} \rightarrow\rho_{loc} </math> for every anisotropy coefficient analyzed, what demonstrates the robustness of the methodology assessed.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">

[[Image:draft_Vassoler Rutz_344011008-image193.jpeg|408px]] </div>

{| class="formulaSCP" style="width: 100%;margin: 1em auto 0.1em auto;width: 100%;text-align: center;"

|  

{| style="text-align: center; margin:auto;width: 100%;"

|-

|Figure 7: <math>{{\rho }_{loc}}</math> and <math>\rho_h</math> versus anisotropy coefficients <math>\bigl(\varepsilon\bigr)</math> for different number of grid points.

Next section presents the complexity analysis of multigrid. For the analysis, multigrid was built with the components that had the best convergence factors, according to LFA. In addition, a comparison between partial weighting and full weighting will be presented.

In order to assess the effect of the number of unknowns on CPU time, optimum components obtained by LFA were used. Fig. 8(a) and Fig. 8(b) show, for <math>\mbox{FW}</math> and  <math display="inline">{\mbox{PW}}_\mbox{x}</math> restrictions respectively, that for the anisotropic problem <math>\bigl(\varepsilon=1\bigr)</math>, the <math display="inline">t_{CPU}</math> is not lower. As the problem becomes more anisotropic <math>\bigl(0<\varepsilon<<1\,\,\,\text{or}\,\,\,\varepsilon>>1\bigr) </math>, the <math>t_{CPU}</math> decreases for every ''N ''value assessed. For every anisotropy coefficient assessed, the <math>t_{CPU}</math> with <math>\mbox{FW}</math> restriction is very similar to the <math>t_{CPU}</math> with <math display="inline">{\mbox{PW}}_\mbox{x}</math> restriction, that is,  <math display="inline">t_{CPU}\left(FW\right)\approx t_{CPU}\left({\mbox{PW}}_\mbox{x}\right)</math> .

It is also observed for symmetric anisotropies <math>\bigl(\varepsilon ={{10}^{-\kappa }}\,\,\,\text{and}\,\,\,\varepsilon ={{10}^{\kappa }}\bigr)</math> with <math>\kappa\in\{1,2,3,4\}</math>, that the values of <math>t_{CPU}</math> obtained are extremely similar.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">

| [[Image:draft_Vassoler Rutz_344011008-image206.jpeg|288px]]

| [[Image:draft_Vassoler Rutz_344011008-image207.jpeg|center|282px]]

|}

{| class="formulaSCP" style="width: 100%;margin: 1em auto 0.1em auto;width: 100%;text-align: center;"

|-

|  

{| style="text-align: center; margin:auto;width: 100%;"

|-

|Figure 8: CPU time versus number of nodes (''N'').

One can observe in Tab. 1 that, for every anisotropy employed, the multigrid method has a good performance, since <math>p\approx1</math> in every case. These results prove the efficiency and robustness of Algorithm 1, proposed in this work.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">

{| style="width: 76%;margin: 1em auto 0.1em auto;border-collapse: collapse;"   

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;" |<span style="text-align: center; font-size: 75%;"> </span><math>10^{-2}</math>

|}</div>

The values obtained for the convergence factor, presented in section 4.1, and for the complexity order concerning to the <math>\text{PW}_x</math> and <math>\mbox{FW}</math> restriction operators (Tab. 1) are quite similar and thus, insufficient to decide which one results in a more efficient algorithm.

These arithmetical operations concern to floating point operations (flops) performed during the iterative process and are not affect by the hardware used. Each addition, multiplication and division operation correspond to 1 flop.

Tests were carried out for <math>N_{10}=10</math> (<math>N_{10}</math> is the number of points of the finest grid, considering a problem whose maximum number of levels is <math>L_{\text{max}}=10</math>) and for some values of <math>\varepsilon</math>. Tab. 2 presents the ratio between number of flops of a V-cycle and number of points of the finest grid <math>N_{10}</math>. Tab. 3 shows the ratio between number of flops performed in each restriction and the number of points of the finest grid <math>N_{10}</math>.<div class="center" style="width: auto; margin-left: auto; margin-right: auto;"> 

{| style="width: 76%;margin: 1em auto 0.1em auto;border-collapse: collapse;"   

{| style="width: 76%;margin: 1em auto 0.1em auto;border-collapse: collapse;"  

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;width: 25%;"|<math>\varepsilon</math>

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;width: 25%;"| <math display="inline">\mbox{flops}({\mbox{PW}}_\mbox{x})/N_{10}</math>  

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;width: 25%;"| <math display="inline">\mbox{flops}(\mbox{FW})/N_{10}</math>  

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;"|<math>10^{-2}</math>

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;vertical-align: top;"|'''<math>11.57607615</math>'''

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;vertical-align: top;"|<math>44.65057942</math>

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;"> </span><math>10^{-1}</math>

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;vertical-align: top;"|'''<math>13.89129130</math>'''

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;vertical-align: top;"|<math>53.58069530</math>

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;width: 25%;"| <math>1</math>  

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;"|'''<math>18.37833483</math>'''

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;"|<math>62.02688007</math>

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;width: 25%;"|<math>10^{1}</math>

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;vertical-align: top;"|'''<math>13.89129137</math>'''

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;vertical-align: top;"|<math>53.58069530</math>

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;width: 25%;"| <math>10^{2}</math>  

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;vertical-align: top;"|'''<math>11.57607615</math>'''

| style="border-top: 1pt solid black;border-bottom: 1pt solid black;text-align: center;vertical-align: top;"|<math>44.65057942</math>

The remaining anisotropy coefficients assessed showed similar performances to those presented in Fig. 5 and Tables 2 and 3, what confirms the efficiency and robustness of the algorithm proposed, in addition to the low computational cost with the use of the <math display="inline">{\mbox{PW}}_\mbox{x}</math> operator.

- With <math>\mbox{FW}</math> restriction,  <math display="inline">{\mbox{ILU}}_{\mbox{EN}}</math> for <math>0<\varepsilon<<1</math> and <math>{\mbox{ILU}}_{\mbox{NE}}</math> for <math>\varepsilon>>1</math>, it can be concluded that the 7-point and bilinear prolongation operators presented a similar performance, and for every value of  <math>\varepsilon</math> assessed, <math>\rho_{loc}<<1</math> was obtained. 

- With bilinear interpolation, <math display="inline">{\mbox{ILU}}_{\mbox{EN}}</math> for <math>0<\varepsilon<<1</math> and <math>{\mbox{ILU}}_{\mbox{NE}}</math> for <math>\varepsilon>>1</math>, it can be stated that the lowest values of <math>{{\rho }_{loc}}</math> are obtained with <math>\mbox{FW}</math> and <math display="inline">{\mbox{PW}}_\mbox{x}</math> restriction operators, and that the values of  <math>{{\rho }_{loc}}</math> with these operators are very similar.   

- Using Algorithm 1, <math>{{\rho }_{loc}}\approx{{\rho }_{h}}<<1</math>  for every anisotropy coefficient assessed and <math>{{\rho }_{h}}\rightarrow{{\rho }_{loc}}</math> as the grid becomes more refined.

- The  <math display="inline">t_{CPU}\left(\mbox{FW}\right)\approx t_{CPU}\left({\mbox{PW}}_\mbox{x}\right)</math> for every value of  assessed.

- The complexity order <math>p</math> of the multigrid method with Algorithm 1 is close to one for every anisotropy assessed. For <math>\varepsilon=10^{-4}</math>, for example, <math>p=1.07747</math> with this algorithm.

- The computational cost of multigrid depends on the number of flops of the restriction in a V-cycle. Using Algorithm 1 with  <math display="inline">{\mbox{PW}}_\mbox{x}</math> restriction, the computational cost is 75% lower than with <math>\mbox{FW}</math> restriction.

- The Algorithm 1 with  <math display="inline">{\mbox{PW}}_\mbox{x}</math> restriction proposed in this work is efficient, robust and has low computational cost.

:[1] T. Gradl, K. Klamroth, U. Rüde, U. Optimizing the number of multigrid cycles in the full multigrid algorithm. Numerical Linear Algebra with Applications. Vol. 17 (2010) 199–210.

:[2] R. H. Pletcher, J. C. Tannehill, D. A. Anderson, Computational Fluid Mechanics and Heat Transfer, 3ª ed. CRC Press, USA, 2013.

:[3] G. H. Golub, J. M. Ortega, Scientific Computing and Differential Equations: an Introduction to Numerical Methods, Academic Press, 1992.

:[4] Y. Saad, Iterative Methods for Sparse Linear Systems, 2ªed., PWS, Philadelphia, 2003.

:[5] W. L. Briggs, V.E. Henson, S.F. Mccormick, A Multigrid Tutorial, 2ª ed., SIAM, USA, 2000.

:[6] U. Trottenberg, C. Oosterlee, A. Schüller, Multigrid, Academic Press, England, 2001.

:[7] P. Wesseling, An Introduction to Multigrid Methods, John Wiley & Sons, England, 1992.

:[8] F. Oliveira, M. A. V. Pinto, C. H. Marchi, L. K. Araki. Optimized partial semicoarsening multigrid algorithm for heat diffusion problems and anisotropic grids. Applied Mathematical Modelling. Vol. 36 (2012) 4665–4676.

:[9] J. A. Rabi, M. J. S. de Lemos. Optimization of convergence acceleration in multigrid numerical solutions of conductive-convective problems. Applied Mathematics and Computational. Vol. 124 (2001) 215-226.

:[10] R. Wienands, W. Joppich, Practical Fourier Analysis for Multigrid Methods, CRC Press, USA, 2005.

:[11] K. Johannsen. A robust 9-point ILU smoother for anisotropic problems, IWR Preprint, University of Heidelberg, 2005.

:[12] S. A. Vinogradova, L. A. Krukier, The use of incomplete LU decomposition in modeling convection-diffusion processes in an anisotropic medium. Mathematical Models and Computer Simulations. Vol. 5 (2013) 190-197.

:[13] G. Vassoler-Rutz, M. A. V. Pinto, R. Suero, Comparison of the physical anisotropy of multigrid method for two-dimensional diffusion equation, in: Proceedings of COBEM, Rio de Janeiro, Brazil, Dezembro 6-11.

:[14] M. A. V. Pinto, C. Rodrigo, F. J. Gaspar, C.W. Oosterlee. On the robustness of ILU smoothers on triangular grids, Applied Numerical Mathematics. Vol. 106 (2016), 37-52.

:[15] S. R. Franco, F. J. Gaspar, M. A. V. Pinto, C. Rodrigo. Multigrid method based on a space-time approach with standard coarsening for parabolic problems. Applied Mathematics and Computation. Vol. 317 (2018) 25-34.

:[16] F. Oliveira. Effect of Two-Dimensional Anisotropic Meshes on the Performance of the Geometric Multigrid Method. Tese de doutorado, UFPR, 2010. ''In portuguese''.

:[17] P. Wesseling, C. W. Oosterlee. Geometric Multigrid with Applications to Computational Fluid Dynamics. Journal of Computation and Applied Mathematics. Vol. 128 (2001) 311-334.