key: cord-0058887-6jhg1b7d authors: Robaina, D. T.; de Oliveira, S. L. Gonzaga; Kischinhevsky, M.; Osthoff, C.; Sena, A. title: A Convergence Analysis of a Multistep Method Applied to an Advection-Diffusion Equation in 1-D date: 2020-08-24 journal: Computational Science and Its Applications - ICCSA 2020 DOI: 10.1007/978-3-030-58799-4_1 sha: ffcf22e4a37cc6343ea2628f12de377fa2f16426 doc_id: 58887 cord_uid: 6jhg1b7d This paper describes a method for convection-dominated fluid or heat flows. This method relies on the Hopmoc method and backward differentiation formulas. The present study discusses the convergence of the method when applied to a convection-diffusion equation in 1-D. The convergence analysis conducted produced sufficient conditions for the consistency analysis and used the von Neumann analysis to demonstrate that the method is stable. Moreover, the numerical results confirmed the conducted convergence analysis. The efficient numerical solution of evolutionary differential equations is essential in several areas in engineering and science. The Hopmoc method (see [1] and references therein) is a fast and accurate method to solve convection-dominated fluid or heat flows. The method is in an implicit numerical algorithm. Thus, the nodal update formulas employed are independent and can be used simultaneously at all mesh nodes. Consequently, the Hopmoc method can benefit from parallel computing, which is currently a crucial characteristic in the modern multicore architecture [2] . The Hopmoc method employs finite-difference techniques similar to the Hopscotch method [3, 4] , which is applied to solve parabolic and elliptic partial differential equations. The Hopmoc method divides the set of unknowns into two subsets alternately approximated. Thus, the method divides each time step into two semi-steps. For example, consider the use of a quadrangular mesh for the solution of a 2D problem. In this scenario, an internal mesh node belongs to one of the subsets, and its four adjacent mesh nodes belong to the other subset. At each time semi-step, the variables contained in a subset are alternately updated using symmetrical explicit and implicit approaches. More specifically, the first time semi-step updates a subset of unknowns using an explicit approach. Since the second implicit time semi-step uses the solution calculated in the previous time semi-step, no linear system is solved. Moreover, the method evaluates semi-steps along with characteristic lines employing concepts of the modified method of characteristics (MMOC) [5] . Specifically, the Hopmoc method uses approximated solutions from previous time steps along the directional derivative following the characteristic line comparably to the MMOC. Therefore, the Hopmoc method employs a semi-Lagrangian approach. Moreover, the method uses a Eulerian structure, but the discrete equations come from a Lagrangian frame of reference. More precisely, the Hopmoc method employs a spacial discretization along a characteristic line from each mesh node. The method is first-order accurate in space and time. Backward differentiation formulas (BDFs) are implicit methods for the numerical integration of differential equations. BDFs are linear multistep methods that use information from previous time steps to increase the accuracy of an approximation to the derivative of a given function and time. A recent publication integrated the Hopmoc method and BDFs [6] . We referred to the approach as the BDFHM method. This paper presents a convergence analysis of the BDFHM method. The consistency and stability analyses rely on the techniques employed by Oliveira et al. [1] and Zhang [7] , respectively. This paper is organized as follows. In Sect. 2, the BDFHM method is presented. In Sect. 3, the convergence analysis of the method is provided. Finally, In Sect. 4, the conclusions and future directions in this investigation are discussed. In this section, we show a solution of the 1-D advection-diffusion equation using the BDFHM method, where d is the diffusion coefficient, v is a constant positive velocity, and 0 ≤ x ≤ 1. The advection-diffusion equation is of main importance in many physical systems, especially those involving fluid flow. For instance, in computational hydraulics and fluid dynamics problems, the advection-diffusion equation may be seen to represent quantities such as mass, heat, energy, vorticity, etc. [8] . In Eq. (1), u t refers to the time derivative and not u evaluated at the discrete-time step t. Nevertheless, we abuse the notation and now use t to denote a discrete-time step so that 0 ≤ t ≤ T , for T time steps. The unit vector τ = (v · δt, δt) = x − x, t n+ 1 2 − t n represents the characteristic line associated with the transport u t + v · u x , and x (x) is the "foot" of the characteristic line in the second (first) time semi-step. The derivative in the direction of τ is given by From the diffusion equation along the characteristic line [9] , the modified method of characteristics approximates the directional derivative in explicit form through the equation For clarity, we use a notation with overlines (to indicate for example the foot of the characteristic line that is calculated by an interpolation method) and Substituting τ = δt · (v) 2 + 1 in Eq. (2) yields u . Similarly, one can obtain a discretization of the Laplace operator on an implicit form by means of the equation u . Likewise, the difference operator for the BDFHM can be defined as When using operator (3), two time semi-steps can be represented as 3 2 u where δt = Δt 2 and θ n i = 1 (0) if n + i is odd (even). We describe a complete time step of the BDFHM method as follows. 1. Initialize x and x (e.g. using the Hopmoc method) at times steps t − 1 2 and t 0 , respectively. 2. Obtain u for all N mesh nodes (1 ≤ i ≤ N ) x i (e.g. using an interpolation method). In particular, the BDFHM method uses two interpolations in the first time semi-step, i.e., it uses an interpolation method to calculate u n and u n− 1 2 to obtain u n+ 1 2 . In the second time semi-step, no interpolation method is used since u n+ 1 2 and u n (that are used to obtain u n ) were calculated in the first time semi-step. 3. Calculate (alternately) u n+ 1 2 i using the explicit (implicit) operator for mesh nodes n + 1 + i that belong to the odd (even) subset. 4. Calculate (alternately) u n+1 i using the implicit (explicit) operator for mesh nodes n + 2 + i that belong to the odd (even) subset. In steps (3) and (4), the explicit approach uses the values from adjacent mesh nodes. The strategy updated these adjacent mesh nodes in the previous time step. The implicit approach uses values from adjacent mesh nodes that were updated in the current time step using the explicit approach. Therefore, no linear system is solved when applying the BDFHM method. The Hopmoc method takes O(T · n) time since the 1-D Hopmoc method computes five loops that iterate n 1-D stencil points inside a time loop [10] . The use of BDFs does not modify the complexity of the 1-D Hopmoc method. The reason is that, similar to the MMOC, the loop that computes a BDF takes O(n) time. In Sect. 3.1, we demonstrate a consistency analysis of the BFD-Hopmoc method using Taylor's series expansion of an expression involving two consecutive time semi-steps. In Sect. 3.2, we show a von Neumann stability analysis of the BFD-Hopmoc method. A numerical method is convergent if the numerical solution approximates the analytical solution of the partial differential equation when Δx → 0. In this section, we demonstrate the consistency of the BDFHM method using Taylor's series expansions of the terms from the implicit formula. Let's and u n+ 1 be two consecutive time semi-steps of the BDFHM method. Isolating the unknown variable u Substituting Eq. (6) in Eq. (4) yields When using Taylor's series expansions in each term regarding to the node mesh (x i , t n ), one obtains where: Rewriting the selected terms (highlighted with overbraces) in this equation yields Simplifying Eq. (12) and, since h 2 = (Δx) 2 , one obtains When observing the resulting terms, the error associated with the BDFHM method can be written as In Eq. (14), we highlighted terms with Δx in the denominator with an overbrace. In the same equation, we highlighted with a double overbrace the terms that can be simplified. Similarly, we highlighted with overlines the terms that we will develop. Simplifying Eq. (14) produces This study safely allows us to conclude that r < 1, m < r < r 2 3 < r 1 2 < r 1 3 ⇒ m < r. Therefore, the sufficient consistency condition for the BDFHM method is that δt → 0 faster than Δx → 0, i.e., lim δt,Δx→0 δt Δx = 0. Different techniques can be used to evaluate the stability of a method. For example, Oliveira et al. [1] demonstrated the stability of the Hopmoc method utilizing a spectral condition involving the values of Δt and Δx. Another example is a technique proposed by Zhang [7] . This technique is based on the decomposition of operators to prove the stability of a second order time multistep method, which was applied to the parallel solution of the wave equation. Moreover, this strategy uses the von Neumann stability analysis [11] . The von Neumann stability analysis determines the stability (or instability) of a finite-difference approximation. In a finite-difference approximation, a solution of the finite-difference equation is expanded in a Fourier series. Thereby, this present stability analysis is based on the techniques presented by Zhang [7] . For clarity, we show Eqs. (4) and (5) again below. Thus, taking into account the strategy proposed by Zhang [7] , consider two time semi-steps of the BDFHM method, Convergence analysis of the Hopmoc method Tuning up TVD Hopmoc method on Intel MIC Xeon Phi architectures with Intel Parallel Studio Tools Nonsymmetric difference equations Hopscotch: a fast second order partial differential equation solver Numerical methods for convection-dominated diffusion problems based on combining the method of characteristics with finite element or finite difference procedures Numerical simulations of the 1-D modified Burgers equation The multistep finite difference fractional steps method for a class of viscous wave equations A new difference scheme with high accuracy and absolute stability for solving convection diffusion equations An Introduction to the Method of Characteristics Hybrid MPI/OpenMP/OpenACC implementations for the solution of convection diffusion equations with Hopmoc method Numerical integration of barotropic vorticity equation High resolution schemes for hyperbolic conservation laws 2 2 uxx| n+1 i + 7 9 d (Δx) 2 (v · δt) 2 2Rewriting the selected terms (highlighted with overbraces) in (15) producesTaking into account Eq. (13), one obtains + 4When replacing this expression by Eq. (13) in , the error can be written asTherefore, the truncation error isThe analysis allowed us to conclude that the BDFHM method has the following truncation errorThe BDFHM method is consistent if lim Δx→0 = 0. More specifically, the local truncation error [i.e., each term in Eq. (16)] must tend to zero when Δx → 0 for the discretization to be consistent with the partial differential equation. Using the technique employed by Oliveira et al. [1] , which is based on the parametrization of the time-space discretization, a sufficient consistency condition is that δt tends to zero faster than Δx, i.e., lim δt,Δx→0 δt Δx = 0. Similar to the analysis conducted by Oliveira et al. [1] , consider m = p and r = q , where p and q are positive integers, 0 < < 1, and → 0. Assume that m tends to zero faster than r. Thus, p < q , that is, p > q, which is required for the consistency analysis [1] . Consider, for example, the term δt Δx . Note that lim r,m→0for a constant c, i.e.-if r → 0 similar to m → 0, i.e p = q, then the limit is a constant non-null value; -if r → 0 faster than m → 0, i.e., p < q, then the limit diverges; -if r → 0 slower than m → 0, i.e., p > q, then the limit is zero.Thus, consistency is not verified if p ≤ q. Therefore, supposing that p > q, one can analyze under which conditions occurs → 0. Substituting m = p and r = q in each term of in Eq. (17) (following the strategy proposed by Oliveira et al. [1] ) yieldsWhen considering uwhere k x is the number of wavelengths per unit distance, expression (25) can be rewritten asand. It is concluded thatThen, the analysis of the radicals of each eigenvalue allows us to conclude that: i ) if Λ > 0, then. Thus, |λ 1,2 | ≤ 737 1089 ≤ 1. Therefore, based on the von Neumann stability analysis [11] , we conclude that the BDFHM method is stable. The BDFHM method integrates the Hopmoc method and backward differentiation formulas. The consistency and stability analyses of the BDFHM method confirmed that the BDFHM method is convergent. Similar to the consistency analysis presented by Oliveira et al. [1] , we used the parametrization of the error as a function of time and space discretization. Additionally, the stability analysis follows a technique employed by Zhang [7] . In particular, the use of backward differentiation formulas did not improve the accuracy of the standard Hopmoc method, i.e., the BDFHM method is first-order accurate in space and time.We intend to study the BDFHM method in conjunction with total variation diminishing techniques [12] and flux-limiting procedures to improve the accuracy results. We also intend to analyze the 2-D BDFHM method applied to stiff problems.