Improved Semi-Lagrangian Methods And Its Applications

This dissertation mainly study how to use adaptivity and parallelization in a integrated and systematic fashion to revitalize Semi-Lagrangian method. By these new techniques, we hope the cost-effectiveness, accuracy and applicability of the Semi-Lagrangian method will be intrinsically improved. We simplify the proof of theε-uniform convergence results and present aε-uniform priori error estimate without extra requirement of the regularity of the exact solution. According to the nature of the convection-dominated problem and the Semi-Lagrangian method, we develop a new time error indicator and its a posteriori error estimates. Based on this new time error indicator, we give a priori error estimate with optimal convergence rate and minimal requirement of the regularity. We use finite element method for spacial discretization and give a posteriori error estimate for the fully discretized scheme. Meanwhile, we improve the classical time parallel algorithm by introducing time adaptivity. We apply Semi-Lagrangian method to the Non-Newtonian fluids simulation. We proposed the algorithms, implement details and numerical results.Semi-Lagrangian method is firstly proposed in the early 80s [36, 80]. It dis-cretizes the convection and the time derivative simultaneously, and the temporal discretization is done along the characteristics. Since this method is based on the Lagrangian point of view, it can linearize and symmetrize the original problem. If exact integration is used, this scheme is unconditionally stable and relatively large time step size is allowed. Semi-Lagrangian method has been applied to many different problems, such as the convection diffusion problems [96, 13, 97], incompressible fluids simulation [80, 17, 1, 78, 99] and viscoelastic fluids simulations [77, 78, 62, 41]. For the priori error estimates for L~∞([0,T];L~2(Ω)) norm, mathematicians have the following results with optimal convergence rate [36, 89, 35],where linear finite element space is used. Here, unfortunately, the constant c depends on s inversely, which means this error estimates is meaningless whenε→0. Therefore,ε-uniform error estimates is proposed by [11],But this result requires extra regularity of the exact solution. In chapter 2, we simplify the proof, obtain the similar results without any extra regularity requirements. Although this result is suboptimal in the convergence rate, it is more reasonable according to the numerical results.Researchers also find some drawbacks of the Semi-Lagrangian method [22, 6, 10, 5] which would limit the applications of the method. Since we have to use numerical integration or interpolation, numerical diffusion will be introduced. The scheme also may become conditionally unstable. Furthermore, uniform grid does not suit the shock layers or moving fronts which usually occur in the convection dominated case. In order to overcome these drawbacks, researchers introduced some new methods such as artificial diffusion method, high resolution scheme, moving finite element method and streamline method. And adaptivity also has been introduced into the Semi-Lagrangian method [33, 26, 49, 24, 25]. Adaptive algorithm modifies the spacial mesh and time step size according to the error information which is provided by the current numerical solution, therefore it shows its potential and validity. However, for time, these results use the classical time error indicator which is originally proposed for the parabolic problem. This kind of time a posteriori error estimators does not take the characters of the convection dominated problems into account and may not efficient. Notice that the convection diffusion problem satisfies the energy identity along the characteristics, in Chapter 3, we proposed a new time error indicator and its a posteriori error estimates. Combining it with residual type space error indicator, we give a posteriori error estimates for the fully discretized scheme and the corresponding adaptive algorithm. Additionally, based on this new time error indicator, we present a priori error estimate in time with optimal order of convergence rate and minimal requirement of the regularity. This overcomes the drawback that classical analysis requires extra regularity.Another big concern about the Semi-Lagrangian method is the computa- tional overhead. Compare with standard time discretize scheme, the Semi-Lagrangian method have to backtracking the characteristics at each time step which increases the overall computational time. Moreover, when we deal with complex problems, time marching do take a long time when we use small time step size due to the stability issue. Sometimes we can not get a reasonable results in a real time. Therefore, we introduce parallel algorithm in time to the Semi-Lagrangian method. Parareal is firtly proposed in [65] and has been applied to many different problems [9, 7, 67, 44, 31]. This algorithm is a iteration method based on two time grid. At each iteration, we first predict on the coarse grid with large time step size and then correct on the fine grid with small time step size concurrently. In Chapter 4, from the linear iteration method point of view, we analysis the Parareal algorithm and give a new proof of the convergence results. Since the Semi-Lagrangian method solves a parabolic problem at each time step. we can apply parallel algorithm directly. Because of the hyperbolic nature of the solution of the convection diffusion equation, we introduce the time adaptivity to the Parareal algorithm. According to the different purpose of the two grid, we design different time adaptive algorithms for them respectively. Time Adaptive Parareal algorithm balances the computational load on each processors and optimize the efficiency of the parallel algorithm. Moreover, adaptivity improves the applicability of the Parareal algorithm.We apply the Semi-Lagrangian method to the Non-Newtonian Fluids simulation . The difficulties of this simulation are that we should preserve the positivity of the conformal stressτ_A and the stability issue when the Weissenberg number is relatively big (Wi> 0.7). If a numerical algorithm can not preserve the positivity, this algorithm may not converge, especially when the Weissenberg number is large. The Semi-Lagrangian method can preserve the positivity naturally [63, 62]. In Chapter 5, we discuss the procedures of the algorithm and some implement details. The numerical results show that our scheme is effective. When Weissenberg number is smaller then 0.7, we get the same results with others and when Weissenberg number is large, our method is stable and effective.This thesis is a phased summary of the author's research during his visit in the Pennsylvania State University. The author's research is under Prof. Jinchao Xu's supervision and is still under way.