Well-balanced Positivity Preserving Central-Upwind Scheme on Triangular Grids for the Saint-Venant System, submitted
||x - x||L2N ≤ C inf(z ∈ Εk) ||x - z||L2Nwith high probability on the draw of Φ. Here, Εk consists of all vectors with at most k nonzero coordinates. The first result of this type was proved by Wojtaszczyk [19] who showed this property when η is a normalized Gaussian random variable. We extend this property to more general random variables, including the particular case where η is the Bernoulli random variable which takes the values ±1/√n with equal probability. The proofs of our results use geometric mapping properties of such random matrices some of which were recently obtained in [14]. Quadrature formulae for Fourier coefficients, submitted We consider quadrature formulas of high degree of precision for the computation of the Fourier coeficients in expansions of functions with respect to a system of orthogonal polynomials. In particular, we show the uniqueness of a multiple node formula for the Fourier-Tchebyche coeficients given by Micchelli and Sharma and construct new Gaussian formulas for the Fourier coeficients of a function, based on the values of the function and its derivatives. Central-upwind schemes for two-layer shallow water equations, to appear. We derive a second-order semi-discrete central-upwind scheme for one- and two-dimensional systems of two-layer shallow water equations. We prove that the presented scheme is wellbalanced in the sense that stationary steady-state solutions are exactly preserved by the scheme, and positivity preserving, that is, the depth of each fluid layer is guaranteed to be nonnegative. We also propose a new technique for the treatment of the nonconservative products describing the momentum exchange between the layers. The performance of the proposed method is illustrated on a number of numerical examples, in which we successfully capture (quasi) steady-state solutions and propagating interfaces. Fast Explicit Operator Splitting Method for Convection-Diffusion Equations, Int. J. Numer. Meth. Fluids, 59 (2009), no. 3, 309--332. Systems of convection–diffusion equations model a variety of physical phenomena which often occur in real life. Computing the solutions of these systems, especially in the convection dominated case, is an important and challenging problem that requires development of fast, reliable and accurate numerical methods. In this paper, we propose a second-order fast explicit operator splitting (FEOS) method based on the Strang splitting. The main idea of the method is to solve the parabolic problem via a discretization of the formula for the exact solution of the heat equation, which is realized using a conservative and accurate quadrature formula. The hyperbolic problem is solved by a second-order finite-volume Godunov-type scheme. We provide a theoretical estimate for the convergence rate in the case of one-dimensional systems of linear convection–diffusion equations with smooth initial data. Numerical convergence studies are performed for one-dimensional nonlinear problems as well as for linear convection–diffusion equations with both smooth and nonsmooth initial data. We finally apply the FEOS method to the one- and two-dimensional systems of convection–diffusion equations which model the polymer flooding process in enhanced oil recovery. Our results show that the FEOS method is capable to achieve a remarkable resolution and accuracy in a very efficient manner, that is, when only few splitting steps are performed. Streaming surface reconstruction using wavelets, Computer Graphics Forum (Proceedings of the Symposium on Geometry Processing), 27 (2008), no. 5, 1411--1420. We present a streaming method for reconstructing surfaces from large data sets generated by a laser range scanner using wavelets. Wavelets provide a localized, multiresolution representation of functions and this makes them ideal candidates for streaming surface reconstruction algorithms. We show how wavelets can be used to reconstruct the indicator function of a shape from a cloud of points with associated normals. Our method proceeds in several steps. We first compute a low-resolution approximation of the indicator function using an octree followed by a second pass that incrementally adds fine resolution details. The indicator function is then smoothed using a modified octree convolution step and contoured to produce the final surface. Due to the local, multiresolution nature of wavelets, our approach results in an algorithm over 10 times faster than previous methods and can process extremely large data sets in the order of several hundred million points in only an hour. Anisotropic smoothness spaces via level sets, Commun. Pur Appl. Math., 61 (2008), no. 9, 1264--1297. It has been understood for sometime that the classical smoothness spaces, such as the Sobolev and Besov classes, are not satisfactory for certain problems in image processing and nonlinear PDEs. Their deficiency lies in their isotropy. Functions in these smoothness spaces must be simultaneously smooth in all directions. The anisotropic generalizations of these spaces also have the deficiency that they are biased in coordinate directions. While they allow different smoothness in certain directions, these directions must be aligned to the coordinate axes. In the application areas mentioned above, it would be desirable to measure smoothness in new ways which would allow one to have more local control over the smoothness directions. We introduce one possible approach to this problem based on defining smoothness via level sets. We present this approach in the case of functions defined on ℜd. Our smoothness spaces depend on two smoothness indices (s1, s2). The first reflects the smoothness of the level sets of the function, while the second index reflects how smoothly the level sets themselves are changing. As a motivation, we start with d=2 and investigate Besov smooth domains. A Central-upwind scheme for landslides-generated water waves, Hyperbolic Problems: Theory, Numerics, Applications (Lyon, 2006), 635--642, Springer, 2008. We study a simple one-dimensional (1-D) toy model for landslides-generated nonlinear water waves. The landslide is modeled as a rigid bump translat- ing down the side of the bottom while the water motion is modeled by the Saint-Venant system of shallow water equations. The resulting system is nu- merically solved using a well-balanced positivity preserving central-upwind scheme. The obtained numerical results are in good agreement with both the two-dimensional (2-D) incompressible flow numerical simulations and the ex- perimental data. Adaptive semi-discrete central-upwind schemes for nonconvex hyperbolic conservation laws, SIAM J. Sci. Comput., 29 (2007), no. 6, 2381--2401. We discover that the choice of a piecewise polynomial reconstruction is crucial in computing solutions of nonconvex hyperbolic (systems of) conservation laws. Using semi-discrete central-upwind schemes we illustrate that the obtained numerical approximations may fail to converge to the unique entropy solution or the convergence may be so slow that achieving a proper resolution would require the use of (almost) impractically ne meshes. For example, in the scalar case, all computed solutions seem to converge to solutions that are entropy solutions for some entropy pairs. However, in most applications, one is interested in capturing the unique (Kruzhkov) solution that satis es the entropy condition for all convex entropies. We present a number of numerical examples that demonstrate the convergence of the solutions, computed with the dissipative second-order minmod reconstruction, to the unique entropy solution. At the same time, more compressive and/or higher-order reconstructions may fail to resolve composite waves, typically present in solutions of nonconvex conservation laws and thus may fail to recover the Kruzhkov solution. In this paper, we propose a simple and computationally inexpensive adaptive strategy that allows to simultaneously capture the unique entropy solution and to achieve a high resolution of the computed solution. We use the dissipative minmod reconstruction near the points where convexity changes and utilize a fth-order weighted essentially non-oscillatory (WENO5) reconstruction in the rest of the computational domain. Our numerical examples (for one- and two-dimensional scalar and systems of conservation laws) demonstrate the robustness, reliability, and non-oscillatory nature of the proposed adaptive method. A second-order well-balanced positivity preserving central-upwind scheme for the Saint-Venant system, Comm. Math. Sci., 5 (2007), no. 1, 133--160. A family of Godunov-type central-upwind schemes for the Saint-Venant system of shallow water equations has been rst introduced in [A. Kurganov and D. Levy, M2AN Math. Model. Numer. Anal., 36 (2002), pp. 397{425]. Depending on the reconstruction step, the second-order versions of the schemes there could be made either well-balanced or positivity preserving, but fail to satisfy both properties simultaneously. Here, we introduce an improved second-order central-upwind scheme which, unlike its forerunners, is capable to both preserve stationary steady states (lake at rest) and to guarantee the positivity of the computed uid depth. Another novel property of the proposed scheme is its applicability to models with discontinuous bottom topography. We demonstrate these features of the new scheme, as well as its high resolution and robustness in a number of one- and two-dimensional examples. Greedy wavelet projections are bounded on BV, Trans. Amer. Math. Soc., 359 (2007), 637--648. Let BV = BV(IRd) be the space of functions of bounded variation on IRd with d ≥ 2. Let ψλ, λ ∈ Δ, be a wavelet system of compactly supported functions nor- malized in BV, i.e. |ψλ|BV(IRd) = 1, λ ∈ Δ. Each f ∈ BV has a unique wavelet expansion Ελ∈Δ cλ(f)ψλ with convergence in L1(IRd). If ΛN(f) is the set of N indicies λ ∈ Δ for which |cλ(f)| are largest (with ties handled in an arbitrary way), then ζN(f) := Ελ∈Δ cλ(f)ψλ is called a greedy approximation to f. It is shown that |ζN(f)|BV(IRd) ≤ C|f|BV(IRd) with C a constant independent of f. This answers in the affirmative a conjecture of Meyer [15] (see p. 49). Adaptive Central-Upwind Schemes for Hamilton-Jacobi Equations with Nonconvex Hamiltonians, J. Sci. Comput., 27 (2006), 323--333. This paper is concerned with computing viscosity solutions of Hamilton–Jacobi equations using high-order Godunov-type projection-evolution methods. These schemes employ piecewise polynomial reconstructions, and it is a well-known fact that the use of more compressive limiters or higher-order polynomial pieces at the reconstruction step typically provides sharper resolution. We have observed, however, that in the case of nonconvex Hamiltonians, such reconstructions may lead to numerical approximations that converge to generalized solutions, different from the viscosity solution. In order to avoid this, we propose a simple adaptive strategy that allows to compute the unique viscosity solution with high resolution. The strategy is not tight to a particular numerical scheme. It is based on the idea that a more dissipative second-order reconstruction should be used near points where the Hamiltonian changes convexity (in order to guarantee convergence to the viscosity solution), while a higher order (more compressive) reconstruction may be used in the rest of the computational domain in order to provide a sharper resolution of the computed solution. We illustrate our adaptive strategy using a Godunov-type central-upwind scheme, the second-order generalized minmod and the fifth order weighted essentially non-oscillatory (WENO) reconstruction. Our numerical examples demonstrate the robustness, reliability, and non-oscillatory nature of the proposed adaptive method. Finite-Volume-Particle Methods for Models of Transport of Pollutant in Shallow Water, J. Sci. Comput., 27 (2006), 189--199. We present a new hybrid numerical method for computing the transport of a passive pollutant by a flow. The flow is modeled by the Saint-Venant system of shallow water equations and the pollutant propagation is described by a transport equation. The idea behind the new finite-volume-particle method is to use different schemes for the flow and the pollution computations: the shallow water equations are numerically integrated using a finite-volume scheme, while the transport equation is solved by a particle method. This way the specific advantages of each scheme are utilized at the right place. This results in a significantly enhanced resolution of the computed solution. Fast Explicit Operator Splitting Method. Application to the Polymer System, Proceedings of the Fourth International Symposium on Finite Volumes for Complex Applications, Marrakech, 63--72,2005. Computing solutions of convection-diffusion equations, especially in the convection dominated case, is an important and challenging problem that requires development of fast, reliable numerical methods. We propose a second-order fast explicit operator splitting (FEOS) method based on the Strang splitting. The main idea of the method is to solve the parabolic problem via a discretization of the formula for the exact solution of the heat equation, which is realized using a conservative and accurate quadrature formula. The hyperbolic problem is solved by a second-order finite-volume Godunov-type scheme. The FEOS method is applied to the one- and two-dimensional systems modeling two phase multicomponent flow in porous media. Our results demonstrate that the method achieves a remarkable resolution and accuracy in a very efficient manner, that is, when only few splitting steps are performed. RÉSUMÉ. Le calcul de solutions d’équations de type convection-diffusion est, specialement dans les cas où les effects convectifs dominent, un problème important et délicat qui requiert le dévelopement de méthodes numériques rapides, précises et robustes. Nous proposons une méthode explicite d’ordre deux de type “operator splitting” basée sur la méthode du “Strang splitting”. L’idée principale est de résoudre un problème parabolique via une discrétisation de l’expression de la solution exacte de l’équation de la chaleur par une méthode d’intégration numérique conservative. Le problème hyperbolique est résolu par un schéma volume finis de type Godunov d’ordre deux. La méthode est appliquée à des systèmes uni et bidimensionels modélisant des écoulements biphasiques en milieu poreux. Nos résultats établissent clairement la remarquable précision et efficacité de la méthode et le fait que seuls quelques pas de “splitting” sont nécessaires. Central-Upwind Schemes on Triangular Grids for Hyperbolic Systems of Conservation Laws, Numer. Methods Partial Differential Equations, 21 (2005), no. 3, 536--552. We present a family of central-upwind schemes on general triangular grids for solving two-dimensional systems of conservation laws. The new schemes enjoy the main advantages of the Godunov-type central schemes—simplicity, universality, and robustness and can be applied to problems with complicated geometries. The “triangular” central-upwind schemes are based on the use of the directional local speeds of propagation and are a generalization of the central-upwind schemes on rectangular grids, recently introduced in Kurganov et al. [SIAM J Sci Comput 23 (2001), 707–740]. We test a second-order version of the proposed scheme on various examples. The main purpose of the numerical experiments is to demonstrate the potential of our method. The more universal “triangular” central-upwind schemes provide the same high accuracy and resolution as the original, “rectangular” ones, and at the same time, they can be used to solve hyperbolic systems of conservation laws on complicated domains, where the implementation of triangular or mixed grids is advantageous. Semi-Discrete Central-Upwind Schemes with Reduced Dissipation for Hamilton-Jacobi Equations, IMA J. Numer. Anal., 25 (2005), 113--138. We introduce a new family of Godunov-type semi-discrete central schemes for multidimensional Hamilton–Jacobi equations. These schemes are a less dissipative generalization of the central-upwind schemes that have been recently proposed in Kurganov, Noelle and Petrova (2001, SIAM J. Sci. Comput., 23, pp. 707–740). We provide the details of the new family of methods in one, two, and three space dimensions, and then verify their expected low-dissipative property in a variety of examples. Extended cubature formula of Turan type (0,2) for the ball, Approximation theory, A volume dedicated to Borislav Bojanov, 64-72, 2004. We construct explicitly an extended cubature of Turan type (0, 2) for the unit ball in ℜ n. It is a formula for approximation of the integral over the ball by a linear combination of surface integrals over m concentric spheres, centered at the origin, of the integrand itself and its Laplacian. This extended cubature integrates exactly all (2m+1)-harmonic functions and hence all polynomials in n variables of degree 4m + 1. Compressible Two-Phase Flows by Central and Upwind Schemes, M2AN Math. Model. Numer. Anal., 38 (2004), no. 3, 477--493. This paper concerns numerical methods for two-phase flows. The governing equations are the compressible 2-velocity, 2-pressure flow model. Pressure and velocity relaxation are included as source terms. Results obtained by a Godunov-type central scheme and a Roe-type upwind scheme are presented. Issues of preservation of pressure equilibrium, and positivity of the partial densities are addressed. High Raleigh Number Convection in a Fluid Saturated Porous Layer, Journal of Fluid Mechanics, 500 (2004), 263-281. The Darcy–Boussinesq equations at infinite Darcy–Prandtl number are used to study convection and heat transport in a basic model of porous-medium convection over a broad range of Rayleigh number Ra. High-resolution direct numerical simulations are performed to explore the modes of convection and measure the heat transport, i.e. the Nusselt number Nu, from onset at Ra =4π2 up to Ra =104. Over an intermediate range of increasing Rayleigh numbers, the simulations display the ‘classical’ heat transport Nu∼Ra scaling. As the Rayleigh number is increased beyond Ra =1255, we observe a sharp crossover to a form fitted by Nu≈0.0174 × Ra0.9 over nearly a decade up to the highest Ra. New rigorous upper bounds on the high-Rayleighnumber heat transport are derived, quantitatively improving the most recent available results. The upper bounds are of the classical scaling form with an explicit prefactor: Nu≤0.0297×Ra. The bounds are compared directly to the results of the simulations. We also report various dynamical transitions for intermediate values of Ra, including hysteretic effects observed in the simulations as the Rayleigh number is decreased from 1255 back down to onset. Cubature formulae for spheres, simplices and balls, J. Comput. Appl. Math. 162 (2004), no. 2, 483--496. We obtain in explicit form the unique Gaussian cubature for balls (spheres) in Rn based on integrals over balls (spheres), centered at the origin, that integrates exactly all m-harmonic functions. In particular, this formula is exact for all polynomials in n variables of degree 2m − 1. A Gaussian cubature for simplices is also constructed. Upper bounds for the errors for certain smoothness classes are derived. Uniqueness of the Gaussian extended cubature for polyharmonic functions, East J. Approx. 9 (2003), no. 3, 269--275. We introduce a new representation formula for the polyharmonic func- tions of order m. We use it to prove the uniqueness of the Gaussian extended cubature for the unit ball in ℜn that is exact for all 2m- harmonic functions and is based on surface integrals over m spheres. Best basis selection for approximation in Lp, Found. Comput. Math. 3 (2003), no. 2, 161--185. We study the approximation of a function class F in Lp by choosing first a basis B and then using n-term approximation with the elements of B. Into the competition for best bases we enter all greedy (i.e., democratic and unconditional [20]) bases for Lp.We show that if the function class F is well-oriented with respect to a particular basis B then, in a certain sense, this basis is the best choice for this type of approximation. Our results extend the recent results of Donoho [9] from L2 to Lp, p ≠ 2. Cubature formulae for the sphere and the ball in ℜn, Proceedings volume of ``Constructive Theory of Functions'', Varna 2002, (B. Bojanov, Ed.), DARBA, Sofia, 380-384, 2003. We construct explicitly the unique cubature for the unit ball in ℜn based on integrals over spheres (balls), centered at the origin, that integrates exactly all m-harmonic functions. We show that there are no cubatures of this type with higher degree of precision. In particular, this gives integration rule for all polynomials in n variables of degree 2m − 1 A smoothness indicator for adaptive algorithms for hyperbolic systems, J. Comput. Phys. 178 (2002), no. 2, 323--341. The formation of shock waves in solutions of hyperbolic conservation laws calls for locally adaptive numerical solution algorithms and requires a practical tool for identifying where adaption is needed. In this paper, a new smoothness indicator (SI) is used to identify “rough” solution regions and is implemented in locally adaptive algorithms. The SI is based on the weak local truncation error of the approximate solution. It was recently reported in S. Karni and A. Kurganov, Local error analysis for approximate solutions of hyperbolic conservation laws, where error analysis and convergence properties were established. The present paper is concerned with its implementation in scheme adaption and mesh adaption algorithms. The SI provides a general framework for adaption and is not restricted to a particular discretization scheme. The implementation in this paper uses the central-upwind scheme of A. Kurganov, S. Noelle, and G. Petrova, SIAM J. Sci. Comput. 23, 707 (2001). The extension of the SI to two space dimensions is given. Numerical results in one and two space dimensions demonstrate the robustness of the proposed SI and its potential in reducing computational costs and improving the resolution of the solution. Semidiscrete central-upwind schemes for hyperbolic conservation laws and Hamilton-Jacobi equations, SIAM J. Sci. Comput. 23 (2001), no. 3, 707--740 (electronic). We introduce new Godunov-type semidiscrete central schemes for hyperbolic systems of conservation laws and Hamilton–Jacobi equations. The schemes are based on the use of more precise information about the local speeds of propagation and can be viewed as a generalization of the schemes from [A. Kurganov and E. Tadmor, J. Comput. Phys., 160 (2000), pp. 241–282; A. Kurganov and D. Levy, SIAM J. Sci. Comput., 22 (2000), pp. 1461–1488; A. Kurganov and G. Petrova, A third-order semidiscrete genuinely multidimensional central scheme for hyperbolic conservation laws and related problems, Numer. Math., to appear] and [A. Kurganov and E. Tadmor, J. Comput. Phys., 160 (2000), pp. 720–742]. The main advantages of the proposed central Linear transport equations with μ-monotone coefficients, J. Math. Anal. Appl. 260 (2001), no. 2, 307--324. We introduce the concept of a μ-monotone function. It allows us to extend the existing theory for Filippov solutions to ODE, linear transport equations, and conservation laws for a wider range of transport velocities (A1,. . .,Ad) and fluxes (f1,. . .,fd). A third-order semi-discrete genuinely multidimensional central scheme for hyperbolic conservation laws and related problems, Numer. Math. 88 (2001), no. 4, 683--729. We construct a new third-order semi-discrete genuinely multidimensional central scheme for systems of conservation laws and related convection-diffusion equations. This construction is based on a multidimensional extension of the idea, introduced in [17] – the use of more precise information about the local speeds of propagation, and integration over nonuniform control volumes, which contain Riemann fans. As in the one-dimensional case, the small numerical dissipation, which is independent of O( 1/Δt), allows us to pass to a limit as Δt ↓ 0. This results in a particularly simple genuinely multidimensional semi-discrete scheme. The high resolution of the proposed scheme is ensured by the new twodimensional piecewise quadratic non-oscillatory reconstruction. First, we introduce a less dissipative modification of the reconstruction, proposed in [29]. Then, we generalize it for the computation of the two-dimensional numerical fluxes. Our scheme enjoys the main advantage of the Godunov-type central schemes – simplicity, namely it does not employ Riemann solvers and characteristic decomposition. Thismakes it a universal method, which can be easily implemented to a wide variety of problems. In this paper, the developed scheme is applied to the Euler equations of gas dynamics, a convectiondiffusion equation with strongly degenerate diffusion, the incompressible Euler and Navier-Stokes equations. These numerical experiments demonstrate the desired accuracy and high resolution of our scheme. The averaging lemma, J. Amer. Math. Soc. 14 (2001), no. 2, 279--296 (electronic). Averaging lemmas arise in the study of regularity of solutions to nonlinear transport equations. The present paper shows how techniques from Harmonic Analysis, such as wavelet decompositions, maximal functions, and interpolation, can be used to prove averaging lemmas and to establish their sharpness. Central schemes and contact discontinuities, M2AN Math. Model. Numer. Anal. 34 (2000), no. 6, 1259--1275. We introduce a family of new second-order Godunov-type central schemes for one-dimensional systems of conservation laws. They are a less dissipative generalization of the central-upwind schemes, proposed in [A. Kurganov et al., submitted to SIAM J. Sci. Comput.], whose construction is based on the maximal one-sided local speeds of propagation. We also present a recipe, which helps to improve the resolution of contact waves. This is achieved by using the partial characteristic decomposition, suggested by Nessyahu and Tadmor [J. Comput. Phys. 87 (1990) 408{463], which is efficiently applied in the context of the new schemes. The method is tested on the one-dimensional Euler equations, subject to di erent initial data, and the results are compared to the numerical solutions, computed by other second-order central schemes. The numerical experiments clearly illustrate the advantages of the proposed technique. Uniqueness of the Gaussian quadrature for a ball, J. Approx. Theory 104 (2000), no. 1, 21--44. We construct a formula for numerical integration of functions over the unit ball in Rd that uses n Radon projections of these functions and is exact for all algebraic polynomials in Rd of degree 2n-1. This is the highest algebraic degree of precision that could be achieved by an n term integration rule of this kind. We prove the uniqueness of this quadrature. In particular, we present a quadrature formula for a disk that is based on line integrals over n chords and integrates exactly all bivariate polynomials of degree 2n-1. Linear transport equations with discontinuous coefficients, Comm. Partial Differential Equations 24 (1999), no. 9-10, 1849--1873. The purpose of the present paper is to introduce an entropy condition which picks out a unique weak solution for any continuous initial condition. This entropy condition will agree with that in [1] in the case the initial condition is Lipschitz. We shall study properties of the entropy solution including: (i) the relationship to conditions for extracting solutions (Filippov (see Conway [2]), reversible (see Bouchut and James [1])), (ii) minimality properties, (iii) properties of the solution operator. Numerical integration over a disc. A new Gaussian quadrature formula, Numer. Math. 80 (1998), no. 1, 39--59. We construct a quadrature formula for integration on the unit disc which is based on line integrals over n distinct chords in the disc and integrates exactly all polynomials in two variables of total degree 2n − 1. On minimal cubature formulae for product weight functions, J. Comput. Appl. Math. 85 (1997), no. 1, 113--121. We derive in a simple way certain minimal cubature formulae, obtained by Morrow and Patterson [2], and Xu [4], using a different technique. We also obtain in explicit form new near minimal cubature formulae. Then, as a corollary, we get a compact expression for the bivariate Lagrange interpolation polynomials, based on the nodes of the cubature. Central-upwind schemes for hyperbolic conservation laws, Proceedings of ``Iterative Methods, Preconditioning & Numerical PDEs'', 105-108, 2004. Here, we illustrate the potential of the second order semi-discrete central-upwind schemes for computing solutions to the Euler equations of gas dynamics with non-convex equation of state which is a challenging problem because of the formation of composite waves. We also demonstrate that these schemes can be applied to problems with complex geometries, where the use of triangular or mixed rectangular-triangular grids is favorable. |
Back to Publications List |