Binary weighted essentially non-oscillatory (BWENO) approximation

Weighted essentially non-oscillatory (WENO) schemes have been mainly used for solving hyperbolic partial differential equations (PDEs). Such schemes are capable of high order approximation in smooth regions and non-oscillatory sharp resolution of discontinuities. The base of the WENO schemes is a non-oscillatory WENO approximation procedure, which is not necessarily related to PDEs. The typical WENO procedures are WENO interpolation and WENO reconstruction. The WENO algorithm has gained much popularity but the basic idea of approximation did not change much over the years. In this paper, we first briefly review the idea of WENO interpolation and propose a modification of the basic algorithm. New approximation should improve basic characteristics of the approximation and provide a more flexible framework for future applications. New WENO procedure involves a binary tree weighted construction that is based on key ideas of WENO algorithm and we refer to it as the binary weighted essentially non-oscillatory (BWENO) approximation. New algorithm comes in a rational and a polynomial version. Furthermore, we describe the WENO reconstruction procedure, which is usually involved in the numerical schemes for hyperbolic PDEs, and propose the new reconstruction procedure based on the described BWENO interpolation. The obtained numerical results show that the newly proposed procedures perform very well on the considered test examples.     

Symmetrical weighted essentially non‐oscillatory‐flux limiter schemes for Hamilton–Jacobi equations

In this paper, we propose a new scheme that combines weighted essentially non‐oscillatory (WENO) procedures together with monotone upwind schemes to approximate the viscosity solution of the Hamilton–Jacobi equations. In one‐dimensional (1D) case, first, we obtain an optimum polynomial on a four‐point stencil. This optimum polynomial is third‐order accurate in regions of smoothness. Next, we modify a second‐order ENO polynomial by choosing an additional point inside the stencil in order to obtain the highest accuracy when combined with the Harten–Osher reconstruction‐evolution method limiter. Finally, the optimum polynomial is considered as a symmetric and convex combination of three polynomials with ideal weights. Following the methodology of the classic WENO procedure, then, we calculate the non‐oscillatory weights with the ideal weights. Numerical experiments in 1D and 2D are performed to compare the capability of the hybrid scheme to WENO schemes. Copyright © 2015 John Wiley & Sons, Ltd.     

Efficient implementation of WENO schemes to nonuniform meshes

Most of the standard papers about the WENO schemes consider their implementation to uniform meshes only. In that case the WENO reconstruction is performed efficiently by using the algebraic expressions for evaluating the reconstruction values and the smoothness indicators from cell averages. The coefficients appearing in these expressions are constant, dependent just on the scheme order, not on the mesh size or the reconstruction function values, and can be found, for example, in Jiang and Shu (J Comp Phys 126:202–228, 1996). In problems where the geometrical properties must be taken into account or the solution has localized fine scale structure that must be resolved, it is computationally efficient to do local grid refinement. Therefore, it is also desirable to have numerical schemes, which can be applied to nonuniform meshes. Finite volume WENO schemes extend naturally to nonuniform meshes although the reconstruction becomes quite complicated, depending on the complexity of the grid structure. In this paper we propose an efficient implementation of finite volume WENO schemes to nonuniform meshes. In order to save the computational cost in the nonuniform case, we suggest the way for precomputing the coefficients and linear weights for different orders of WENO schemes. Furthermore, for the smoothness indicators that are defined in an integral form we present the corresponding algebraic expressions in which the coefficients obtained as a linear combination of divided differences arise. In order to validate the new implementation, resulting schemes are applied in different test examples.      

High order accurate semi-implicit WENO schemes for hyperbolic balance laws

In this paper we propose a family of well-balanced semi-implicit numerical schemes for hyperbolic conservation and balance laws. The basic idea of the proposed schemes lies in the combination of the finite volume WENO discretization with Roe’s solver and the strong stability preserving (SSP) time integration methods, which ensure the stability properties of the considered schemes [S. Gottlieb, C.-W. Shu, E. Tadmor, Strong stability-preserving high-order time discretization methods, SIAM Rev. 43 (2001) 89-112]. While standard WENO schemes typically use explicit time integration methods, in this paper we are combining WENO spatial discretization with optimal SSP singly diagonally implicit (SDIRK) methods developed in [L. Ferracina, M.N. Spijker, Strong stability of singly diagonally implicit Runge-Kutta methods, Appl. Numer. Math. 58 (2008) 1675-1686]. In this way the implicit WENO numerical schemes are obtained. In order to reduce the computational effort, the implicit part of the numerical scheme is linearized in time by taking into account the complete WENO reconstruction procedure. With the proposed linearization the new semi-implicit finite volume WENO schemes are designed.A detailed numerical investigation of the proposed numerical schemes is presented in the paper. More precisely, schemes are tested on one-dimensional linear scalar equation and on non-linear conservation law systems. Furthermore, well-balanced semi-implicit WENO schemes for balance laws with geometrical source terms are defined. Such schemes are then applied to the open channel flow equations. We prove that the defined numerical schemes maintain steady state solution of still water. The application of the new schemes to different open channel flow examples is shown.     

Bounds for a class of linear functionals with applications to Hermite interpolation

A general estimation theorem is given for a class of linear functionals on Sobolev spaces. The functionals considered are those which annihilate certain classes of polynomials. An interpolation scheme of Hermite type is defined inN-dimensions and the accuracy in approximation is bounded by means of the above mentioned theorem. In one and two dimensions our schemes reduce to the usual ones, however our estimates in two dimensions are new in that they involve only the pure partial derivatives.This research was supported in part by the National Science Foundation under grant number N.S.F.-G.P.-9467.     

ON NEW STRATEGIES TO CONTROL THE ACCURACY OF WENO ALGORITHM CLOSE TO DISCONTINUITIES Ⅱ:CELL AVERAGES AND MULTIRESOLUTION

This paper is the second part of the article and is devoted to the construction and analysis of new non-linear optimal weights for WENO interpolation capable of rising the order of accuracy close to discontinuities for data discretized in the cell averages. Thus, now we are interested in analyzing the capabilities of the new algorithm when working with functions belonging to the subspace $L^1\cap L^2$ and that, consequently, are piecewise smooth and can present jump discontinuities. The new non-linear optimal weights are redesigned in a way that leads to optimal theoretical accuracy close to the discontinuities and at smooth zones. We will present the new algorithm for the approximation case and we will analyze its accuracy. Then we will explain how to use the new algorithm in multiresolution applications for univariate and bivariate functions. The numerical results confirm the theoretical proofs presented.     

Linear barycentric rational quadrature

Linear interpolation schemes very naturally lead to quadrature rules. Introduced in the eighties, linear barycentric rational interpolation has recently experienced a boost with the presentation of new weights by Floater and Hormann. The corresponding interpolants converge in principle with arbitrary high order of precision. In the present paper we employ them to construct two linear rational quadrature rules. The weights of the first are obtained through the direct numerical integration of the Lagrange fundamental rational functions; the other rule, based on the solution of a simple boundary value problem, yields an approximation of an antiderivative of the integrand. The convergence order in the first case is shown to be one unit larger than that of the interpolation, under some restrictions. We demonstrate the efficiency of both approaches with numerical tests.     

An efficient WENO scheme for solving hyperbolic conservation laws

In this paper we propose a new WENO scheme, in which we use a central WENO [G. Capdeville, J. Comput. Phys. 227 (2008) 2977-3014] (CWENO) reconstruction combined with the smoothness indicators introduced in [R. Borges, M. Carmona, B. Costa, W. Sun Don, J. Comput. Phys. 227 (2008) 3191-3211] (IWENO). We use the central-upwind flux [A. Kurganov, S. Noelle, G. Petrova, SIAM J. Sci. Comp. 23 (2001) 707-740] which is simple, universal and efficient. For time integration we use the third order TVD Runge-Kutta scheme. The resulting scheme improves the convergence order at critical points of smooth parts of solution as well as decrease the dissipation near discontinuities. Numerical experiments of the new scheme for one and two-dimensional problems are reported. The results demonstrates that the proposed scheme is superior to the original CWENO and IWENO schemes.     

Relaxation WENO schemes for multidimensional hyperbolic systems of conservation laws

We present a class of high‐order weighted essentially nonoscillatory (WENO) reconstructions based on relaxation approximation of hyperbolic systems of conservation laws. The main advantage of combining the WENO schemes with relaxation approximation is the fact that the presented schemes avoid solution of the Riemann problems due to the relaxation approach and high‐resolution is obtained by applying the WENO approach. The emphasis is on a fifth‐order scheme and its performance for solving a wide class of systems of conservation laws. To show the effectiveness of these methods, we present numerical results for different test problems on multidimensional hyperbolic systems of conservation laws. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

An adaptive mesh method for 1D hyperbolic conservation laws

An adaptive method is developed for solving one-dimensional systems of hyperbolic conservation laws, which combines the rezoning approach with the finite volume weighted essentially non-oscillatory (WENO) scheme. An a posteriori error estimate, used to equidistribute the mesh, is obtained from the differences between respective numerical solutions of 5th-order WENO (WENO5) and 3rd-order ENO (ENO3) schemes. The number of grids can be adaptively readjusted based on the solution structure. For higher efficiency, mesh readjustment is performed every few time steps rather than every time step. In addition, a high order conservative interpolation is used to compute the physical solutions on the new mesh from old mesh based on the finite volume ENO reconstruction. Extensive examples suggest that this adaptive method exhibits more accurate resolution of discontinuities for a similar level of computational time comparing with that on a uniform mesh.     

WENO schemes with Lax–Wendroff type time discretizations for Hamilton–Jacobi equations

In this paper, a class of weighted essentially non-oscillatory (WENO) schemes with a Lax–Wendroff time discretization procedure, termed WENO-LW schemes, for solving Hamilton–Jacobi equations is presented. This is an alternative method for time discretization to the popular total variation diminishing (TVD) Runge–Kutta time discretizations. We explore the possibility in avoiding the nonlinear weights for part of the procedure, hence reducing the cost but still maintaining non-oscillatory properties for problems with strong discontinuous derivative. As a result, comparing with the original WENO with Runge–Kutta time discretizations schemes (WENO-RK) of Jiang and Peng [G. Jiang, D. Peng, Weighted ENO schemes for Hamilton–Jacobi equations, SIAM J. Sci. Comput. 21 (2000) 2126–2143] for Hamilton–Jacobi equations, the major advantages of WENO-LW schemes are more cost effective for certain problems and their compactness in the reconstruction. Extensive numerical experiments are performed to illustrate the capability of the method.     

Generalized hessian forC 1,1 functions in infinite dimensional normed spaces

The subject of this paper is the systematic study of second order notions concerning differentiable functions with Lipschitz derivative. The results and notions are motivated by recent papers of Cominetti, Correa and Hiriart-Urruty. The first goal of this paper is the comparison of several known second order directional derivatives. The second goal is the introduction of a generalized Hessian which is a set of certain symmetric bilinear forms. The relation of this generalized Hessian to other existing second order derivatives is also described. The research was supported by a grant from the National Science Foundation NSF-66-2270, which is gratefully acknowledged. Research supported by the Hungarian National Foundation for Scientific Research (OTKA), Grant No. T-016846 and by the Humboldt Foundation.     

Polling systems with state-dependent setup times

We analyze a polling system with multiple stations (queues) attended by a cycling server, in which a setup occurs only when the queue that is polled by the server has one or more customers present. Although such systems are appropriate for modeling numerous manufacturing and telecommunication systems, their analysis is not well developed in the literature. We provide an exact analysis for the 2 station model and present two approximation schemes to determine the mean station waiting times for models with 3 or more stations. We show that some approximate models which have been proposed in the literature for providing upper bounds on the mean station waiting times do not always yield upper bounds. Extensive numerical tests indicate that a simple average of the two approximation schemes yields a close estimate of the true mean station waiting time. This average-of-approximations procedure appears to be robust for a large range of parameter values.Research supported in part by the Natural Sciences and Engineering Research Council of Canada under grant OGP0045904.Research supported in part by the National Science Foundation under grant DMI-9500471.     

Optimization with unary functions

Most nonlinear programming problems consist of functions which are sums of unary functions of linear functions. Advantage can be taken of this form to calculate second and higher order derivatives easily and at little cost. Using these, high order optimization techniques such as Halley's method can be utilized to accelerate the rate of convergence to the solution. These higher order derivatives can also be used to compute second order sensitivity information. These techniques are applied to the solution of the classical chemical equilibrium problem.Supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research and by the Office of Naval Research grant N00014-86-K0052.Supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research.     

An algorithm for nonlinear optimization using linear programming and equality constrained subproblems

This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza [10]. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained by making a linear approximation to the ₁ penalty function inside a trust region. In the second stage, an equality constrained quadratic program (EQP) is solved involving only those constraints that are active at the solution of the linear program. The EQP incorporates a trust-region constraint and is solved (inexactly) by means of a projected conjugate gradient method. Numerical experiments are presented illustrating the performance of the algorithm on the CUTEr [1, 15] test set.This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported in part by the EPSRC grant GR/R46641.These authors were supported by National Science Foundation grants CCR-9987818, ATM-0086579 and CCR-0219438 and Department of Energy grant DE-FG02-87ER25047-A004.Report OTC 2002/4, Optimization Technology CenterTo Roger Fletcher, with respect and admiration     

A class of the fourth order finite volume Hermite weighted essentially non-oscillatory schemes

In this paper, we developed a class of the fourth order accurate finite volume Hermite weighted essentially non-oscillatory (HWENO) schemes based on the work (Computers & Fluids, 34: 642–663 (2005)) by Qiu and Shu, with Total Variation Diminishing Runge-Kutta time discretization method for the two-dimensional hyperbolic conservation laws. The key idea of HWENO is to evolve both with the solution and its derivative, which allows for using Hermite interpolation in the reconstruction phase, resulting in a more compact stencil at the expense of the additional work. The main difference between this work and the formal one is the procedure to reconstruct the derivative terms. Comparing with the original HWENO schemes of Qiu and Shu, one major advantage of new HWENO schemes is its robust in computation of problem with strong shocks. Extensive numerical experiments are performed to illustrate the capability of the method. Corresponding author This work was partially supported by the National Natural Science Foundation of China (Grant No. 10671097), the European project ADIGMA on the development of innovative solution algorithms for aerodynamic simulations, Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry and the Natural Science Foundation of Jiangsu Province (Grant No. BK2006511)     

The shape preserving ang high accuracy approximation with multiquadric

This paper discusses the sufficient conditions for the shape preserving quasi-interpolation with multiquadric. Some quasi-interpolation schema is given such that the interpolation as well as its high derivatives is convergent. Supported by the National Natural Science Foundation of China.     

Extrapolation of the Nédélec element for the Maxwell equations by the mixed finite element method

In this paper, we use the integral-identity argument to obtain asymptotic error expansions for the mixed finite element approximation of the Maxwell equations on a rectangular mesh. The extrapolation method is applied to improve the accuracy of the approximation via an interpolation postprocessing technique. With the extrapolation, the approximation accuracy can be improved from O(h) to O(h ⁴) in the L ²-norm. Illustrative numerical results are given to demonstrate the higher order accuracy of the extrapolation method. This research was supported by the National Natural Science Foundation of China (No.10471103), Social Science Foundation of the Ministry of Education of China (06JA630047), Tianjin Natural Science Foundation (07JCYBJC14300).     

Richardson extrapolation and defect correction of mixed finite element methods for integro-differential equations in porous media

Asymptotic error expansions in the sense of L ^∞-norm for the Raviart-Thomas mixed finite element approximation by the lowest-order rectangular element associated with a class of parabolic integro-differential equations on a rectangular domain are derived, such that the Richardson extrapolation of two different schemes and an interpolation defect correction can be applied to increase the accuracy of the approximations for both the vector field and the scalar field by the aid of an interpolation postprocessing technique, and the key point in deriving them is the establishment of the error estimates for the mixed regularized Green’s functions with memory terms presented in R. Ewing at al., Int. J. Numer. Anal. Model 2 (2005), 301–328. As a result of all these higher order numerical approximations, they can be used to generate a posteriori error estimators for this mixed finite element approximation. This project was supported in part by the Special Funds for Major State Basic Research Project (2007CB8149), the National Natural Science Foundation of China (10471103 and 10771158), the Social Science Foundation of the Ministry of Education of China (Numerical methods for convertible bonds, 06JA630047), the NSERC, Tianjin Natural Science Foundation (07JCYBJC14300), and Tianjin University of Finance and Economics.     

Basis Function Adaptation in Temporal Difference Reinforcement Learning

Reinforcement Learning (RL) is an approach for solving complex multi-stage decision problems that fall under the general framework of Markov Decision Problems (MDPs), with possibly unknown parameters. Function approximation is essential for problems with a large state space, as it facilitates compact representation and enables generalization. Linear approximation architectures (where the adjustable parameters are the weights of pre-fixed basis functions) have recently gained prominence due to efficient algorithms and convergence guarantees. Nonetheless, an appropriate choice of basis function is important for the success of the algorithm. In the present paper we examine methods for adapting the basis function during the learning process in the context of evaluating the value function under a fixed control policy. Using the Bellman approximation error as an optimization criterion, we optimize the weights of the basis function while simultaneously adapting the (non-linear) basis function parameters. We present two algorithms for this problem. The first uses a gradient-based approach and the second applies the Cross Entropy method. The performance of the proposed algorithms is evaluated and compared in simulations. This research was partially supported by the Fund for Promotion of Research at the Technion. The work of S.M. was partially supported by the National Science Foundation under grant ECS-0312921.