## Semi-Lagrangian approximation schemes for linear and Hamilton-Jacobi equations

We also notice that there is a significant difference between the magnitude of the errors if measured over the whole grid or on a region in the interior. It is also at these points that the local consistency error is of order VAx as shown in Corollary 2. In these cases, the error convergence rates are approximately 1. In this section, we study the application of multigrid preconditioners together with policy iteration  to solve the non-linear system 1.

Geometric multigrid requires us to predefine a grid hierarchy based on the geometry of the problem. The variability of the width of the LISL stencil within a given grid variable coefficients and through the grid hierarchy makes it difficult, even for simple problems, to design an appropriate grid hierarchy and a good smoother. Moreover, the varying stencil requires us to build the coarse-grid version of the operator algebraically instead of using its coarse grid version, which further limits our knowledge of the problem as we go deeper into the grid hierarchy.

### Submission history

Another aspect to consider is related to the transfer operators. Standard grid interpolations provide approximations using the grid neighbours of a given node, whereas for the LISL stencil, being non-local, the solution at a given node may not be best approximated by its neighbours on the grid but by those on its stencil. These heuristics suggest that the algebraic approach to multigrid, fixing the smoother and building operator dependent intergrid transfer operators, may result in more efficient multigrid preconditioning for LISL discretizations.

Algebraic multigrid AMG , introduced in , constructs "coarse grids" based on the matrix coefficients. However, as pointed out in Section 6. A slow reduction in the number of unknowns and the use of the Galerkin principle to build the coarse system matrix with intergrid transfer operators using weighted averages increase the complexity of the multigrid scheme. To measure the complexity the following quantities are commonly used:. Definition 3. We will find a benefit to the convergence of constructing the "coarse grids" algebraically already for simple examples of LISL matrices Sect.

Recent and on-going research on algebraic multigrid [24,25] shows how one can construct good multigrid cycles using simplified "intergrid" transfer operators based on aggregation of the unknown variables, thus avoiding the problem of increased complexity on coarser levels. In particular,  proves convergence of a simplified two-grid scheme using aggregation for non-singular M-matrices with non-negative row and column sums. To assess the suitability of preconditioning based on geometric multigrid, we start by considering the spectrum of LISL matrices for a simplified model.

Denote by Ln the following N x N Laplacian matrix. Using the properties of Kronecker products we can characterize the eigenvalues of the matrices L'N in terms of the eigenvalues of the standard Ln matrices. By [A]n xn we mean that we select the first N rows and N columns of A, and similar for [d]n for a vector N.

The plots show that for LISL discretization matrices, in contrast to the standard case, small eigenvalues are not necessarily associated with smooth modes. As a result, these components cannot be represented accurately on the coarse mesh. The spectrum of higher-dimensional constant coefficient Laplacians can be inferred from the spectrum of the one-dimensional matrices by means of Kronecker products. Next, we consider the properties of common smoothers when applied to LISL discretization matrices. We seek to analyse how a varying size stencil affects the properties of the standard Gauss-Seidel smoother.

It is thus convenient to rescale the exponent of y by Ax The functions y are important since, as shown in Lemma 4. This property allows us to associate to each discrete finite difference. With multigrid, the objective of the smoother is to dampen error components not reduced by the coarse grid correction. Therefore, assessing the properties of a given smoother requires fixing the coarse grid correction.

This leads to the definition of low and high frequencies below. Example 3. Similarly, the smoothing factor for the LISL scheme can be derived. In the present case of pure diffusion, Schemes coincide.

The maxima calculated numerically are 0. Figure 4 compares the smoothing factor for the fixed stencil 5 point discretization and a specific semi-Lagrangian stencil. If 01 and 02 have the same sign, then. If, however, 01 and 02 have different signs, then. Geometric VV, v2 and W V1, v2 cycles are considered, where V1 and V2 denote the number of pre- and post-smoothing steps. To account for the fact that 0. The deterioration of the smoother for large mi is present here too.

We conclude the discussion of geometric multigrid by testing its performance against an iterative solver used in , i. These values are chosen to study the effect of interpolation which is always required in the second case and only for odd levels in the first on the convergence and complexity of the methods, in particular on the convergence rates of geometric multigrid and the operator complexity of algebraic multigrid. We use a Cartesian grid with equal number of equispaced nodes in both directions, the smoother is Gauss-Seidel, the prolongation operator bilinear interpolation, the restriction the transpose of the prolongation, and the coarse grid operator is constructed using the Galerkin principle.

We solve the problems above for different. Table 6 The residual reduction factor p for different mesh sizes and different multigrid algorithms, for the two-dimensional Laplace equation; the length of the stencil m as per 3. Table 7 Comparison of the residual reduction factor p for different system sizes and different solvers for the one dimensional Laplace equation. This is due to the lack of. Moreover, as shown in Fig. Regarding the BICGSTAB iterative solver, we observe the benefit of using ILU 0 as pre-conditioner, however, the significant increase in the convergence rate as the mesh is refined and hence the condition number of the matrix increases suggests that convergence is not asymptotically mesh size independent.

Table 8 Comparison of the grid and algebraic complexities as per Definitions 3. Returning to the two-dimensional case, the grid hierarchies in the geometric GMG and algebraic AMG multigrid have 5 levels, including the finest one. In the geometric case, the number of unknowns is 4 times smaller from one level to the next. In the AGMG case, the hierarchy is at most 4 levels deep. Table 8 reports the complexities for the three categories of algorithms considered. The results confirm the assertion in  that AMG coarsening, generally, need not reduce the number of unknowns fast enough.

In this section, we discuss the theoretical foundation of Aggregation-based Multigrid AGMG for our specific application of wide stencil discretisations. The key result is Lemma 3. The non-negativity of the row sums of a LISL discretization matrix is obtained almost by construction. The following analysis of the non-negativity of the column sum makes use of the regularity of the coefficients b and a. In particular, we assume that the coefficients are such that for all p e [[1, P]], and for any mesh points xi, xi and corresponding controls ai ,ai e A and s e[0, T ] we have that.

Remark 3. However, what we require in 3.

1. Next Generation Wireless Networks (The Kluwer International Series in Engineering and Computer Science Volume 598).
2. Swipe to navigate through the articles of this issue.
3. Espen R. Jakobsen - Google Scholar-sitater;
4. Transition to rule of law: On the democratic transformation in Hungary (Philosophiae iuris)!

This situation arises in every step of the policy iteration algorithm: a control vector ai is determined by the optimisation step, and then a linear system with this control vector is solved for x i. Generally, the optimal control is not a Holder continuous function of the space variables, but there are many important examples where it is at least piecewise Holder. It can be seen from the proof below that Proposition 3. LISL discretization matrices need not be irreducible, e. We also assume the use of multi-linear interpolation requiring 2d points to approximate function values in Rd and the use of Cartesian grids.

Proposition 3.

Assume that 3. Proof We carry out the proof for Scheme 2, but an analogous analysis holds for Schemes 1 and 3 in the introduction. We also note that we can restrict the analysis to steps where no truncation is required, as in the case of truncation the weights only contribute positively to the diagonal of the matrix and the right-hand side of the equation see Remark 2.

For simplicity of notation, we omit the dependence of the coefficient functions b and ap on the time variable t and the control. For any two nodes i and i to contribute to the sum of column j, it is necessary that.

Therefore, the bound 3. Therefore, on bounded domains, fully implicit time stepping with policy iteration and AGMG preconditioning is the computationally most efficient overall algorithm among the ones considered. Both of these methods are used as preconditioners for a Krylov subspace method that is assumed to have converged when the relative residual is below The AMG precon-ditioner consists of one iteration of the standard V-cycle with two Gauss-Seidel pre- and post-smoothing steps, whereas AGMG uses one Gauss-Seidel pre- and post-smoothing step and the enhanced multigrid cycles mentioned in the introduction, see [24,25].

chondwelduhickno.cf

## Ebook Semi Lagrangian Approximation Schemes For Linear And Hamilton Jacobi Equations

The problems considered have smooth closed form solutions linear in t. As mentioned in the previous section, we employ policy iteration to solve the resulting non-linear discrete problem. In Fig. Both MG methods provide a solution with the same accuracy as the sparse direct solver. We use equispaced Cartesian grids in space with 81, , and nodes per dimension and one time step. Reducing At makes the system matrix more diagonally dominant and as a consequence easier to precondition. Table 10 and Table 11 report memory consumption and quantities related to the Krylov subspace method and to the coarsening.

The coarsening for both of the methods is stopped when the coarse level system is cheap to solve exactly compared to the starting system, specifically, we stop whenever the number of unknowns at the coarse level is comparable to the cubic root of the initial number of unknowns. The fact that aggregation-based coarsening strategies yield coarse matrices with similar sparsity as the original one. Moreover, AGMG yields shallower hierarchies due to higher coarsening factors. The effect of reducing At is also appreciated in this ratio.

We observe that the direct method's consumption increases dramatically while for the MG methods, we note the relation between the memory requirement and the algebraic complexity of the method. The number of Krylov iterations highlight previous comments on the fact that aggregation-based multigrid methods are not efficient if used as stand-alone solvers: in all test cases, AGMG used more iterations than AMG per policy iteration. However, AGMG used as a preconditioner to a Krylov subspace method provides accurate solutions faster and cheaper than the other two solvers considered. On the finest level, the stencil is close to 11 for Problem A and close to 8 for Problem B.

The last two columns report the grid and algebraic complexity as per Definitions 3. As the full matrix hierarchy was not available from  for AMG, but only the coarsest and finest matrices, the starred algebraic complexities are estimates based on the assumption of a geometrically decreasing complexity between the coarsest and finest level, which is likely to be a significant underestimate. This article discusses two aspects of practical importance associated with wide stencil discretizations of second order non-linear parabolic differential operators.

First, we study the truncation of the stencil for problems on bounded domains, as a result of the method overstepping the boundaries for nodes in a surrounding layer. Our main result details the construction of such truncation and proves that the resulting scheme remains consistent, monotone and conditionally stable. Numerical examples confirm that the truncation improves the accuracy of the approach compared to constant and linear extrapolation of the boundary conditions, and the modification of the CFL condition of the scheme.

Second, motivated by the stringent CFL condition of explicit time stepping schemes, we consider implicit schemes and the application of multigrid methods to solve the resulting discrete non-linear systemof equations efficiently. Using theoretical and empirical arguments,. We show that aggregation-based methods are well suited for the discretization schemes considered and justify their use by proving that under mild conditions on the mesh refinement parameters the LISL discretization matrices are M-matrices with non-negative row and column sums.

The algorithms are shown to compare favourably against AMG and sparse direct solvers. Although we only considered linear interpolation, much of the analysis, including in particular the matrix properties in Sect. To conclude, we emphasise that monotone schemes for general diffusions in two and more dimensions are necessarily non-local, so that the question of boundary truncation is not restricted to the class of schemes studied in this paper. Akian, M.

## Semi Lagrangian Approximation Schemes Linear Hamilton Jacobi by Maurizio Falcone Roberto Ferretti

IEEE Barles, G. Bokanowski, O. SIAM J. Camilli, F. Crandall, G. Numerische Mathematik 75 1 , Crandall, M. Davis, T. ACM Trans. Debrabant, K. Eisenstat, S. Forsyth, P. Finance 11 2 , 1 In: Duan, J. Handbook of computational finance. Springer Handbooks of Computational Statistics, pp. Springer, Berlin Han, D. Hoppe, R. Numerische Mathematik 49 , HSL: A collection of Fortran codes for large scale scientific computation.

Kim, H. Linear Algebra Appl. Kushner, H. Lions, P. Partial Differ. Ma, K. IMA J. Menaldi, J. Control Optim. Motzkin, T. Napov, A. Notay, Y. Oberman, A. Saad, Y. Society for Industrial and Applied Mathematics, Philadelphia Numerical Analysis Vassilevski, P. Warin, X. CC BY. Hybrid Multi-level solvers for discontinuous Galerkin finite element discrete ordinate diffusion synthetic acceleration of radiation transport algorithms. Improved convergence and stability properties in a three-dimensional higher-order ice sheet model. This article is published with open access at Springerlink.

• Spectroscopic Methods and Analyses: NMR, Mass Spectrometry, and Metalloprotein Techniques (Methods in Molecular Biology);
• Sitater per år?
• A dynamic domain decomposition for the eikonal-diffusion equation.