Superconvergent interpolants for collocation methods applied to Volterra integro-differential equations with delay

Standard software based on the collocation method for differential equations delivers a continuous approximation (called the collocation solution) which augments the high order discrete approximate solution that is provided at mesh points. This continuous approximation is less accurate than the discrete approximation. For ‘non-standard’ Volterra integro-differential equations with constant delay, that often arise in modeling predator-prey systems in Ecology, the collocation solution is C ⁰ continuous. The accuracy is O(h ^s+1) at off-mesh points and O(h ^2s ) at mesh points where s is the number of Gauss points used per subinterval and h refers to the stepsize. We will show how to construct C ¹ interpolants with an accuracy at off-mesh points and mesh points of the same order (2s). This implies that even for coarse mesh selections we achieve an accurate and smooth approximate solution. Specific schemes are presented for s=2, 3, and numerical results demonstrate the effectiveness of the new interpolants.     

Error estimation,adaptivity and data transfer in enriched plasticity continua to analysis of shear band localization

In this paper, an adaptive FE analysis is presented based on error estimation, adaptive mesh refinement and data transfer for enriched plasticity continua in the modelling of strain localization. As the classical continuum models suffer from pathological mesh-dependence in the strain softening models, the governing equations are regularized by adding rotational degrees-of-freedom to the conventional degrees-of-freedom. Adaptive strategy using element elongation is applied to compute the distribution of required element size using the estimated error distribution. Once a new mesh is generated, state variables and history-dependent variables are mapped from the old finite element mesh to the new one. In order to transfer the history-dependent variables from the old to new mesh, the values of internal variables available at Gauss point are first projected at nodes of old mesh, then the values of the old nodes are transferred to the nodes of new mesh and finally, the values at Gauss points of new elements are determined with respect to nodal values of the new mesh. Finally, the efficiency of the proposed model and computational algorithms is demonstrated by several numerical examples.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

Approximation of singularly perturbed reaction-diffusion problems by quadratic C 1-splines

Collocation with quadratic C ¹-splines for a singularly perturbed reaction-diffusion problem in one dimension is studied. A modified Shishkin mesh is used to resolve the layers. The resulting method is shown to be almost second order accurate in the maximum norm, uniformly in the perturbation parameter. Furthermore, a posteriori error bounds are derived for the collocation method on arbitrary meshes. These bounds are used to drive an adaptive mesh moving algorithm. Numerical results are presented.     

On regularization in parameter-free shape optimization

This contribution is concerned with a parameter-free approach to computational shape optimization of mechanically-loaded structures. Thereby the term ’parameter-free’ refers to approaches in shape optimization in which the design variables are not derived from an existing CAD-parametrization of the model geometry but rather from its finite element discretization. One of the major challenges in using this type of approach is the avoidance of oscillating boundaries in the optimal design trials. This difficulty is mainly attributed to a lack of smoothness of the objective sensitivities and the relatively high number of design variables within the parameter-free regime. To compensate for these deficiencies, Azegami introduced the concept of the so-called traction method, in which the actual design update is deduced from the deformation of a fictitious continuum that is loaded in proportion to the negative shape gradient. We investigate a discrete variant of the traction method, in which the design sensitivities are computed with respect to variations of the design nodes for a given finite element mesh rather than on the abstract level by means of the speed method. Moreover, the design update process is accompanied by adaptive mesh refinement based on discrete material residual forces. Therein, we consider radaptive node relocation as well as hadaptive mesh refinement. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Iterative method generated by inverse interpolation with additional evaluations

An improvement of the iterative methods based on one point iteration function, with or without memory, using n points with the same amount of information in each point and generated by the inverse polynomial interpolation is given. The adaptation of the strategy presented here gives a new iteration function with a new evaluation of the function which increases the local order of convergence dramatically. This method is generalized to r evaluations of the function. This method for the computation of solutions of nonlinear equations is interesting when it is necessary to get high precision because it provides a lower cost when we use adaptive multi-precision arithmetics. AMS subject classification 65H05     

Adaptive extended isogeometric analysis based on PHT-splines for thin cracked plates and shells with Kirchhoff–Love theory

In this paper, a posteriori error estimation and mesh adaptation approach for thin plate and shell structures of through-the-thickness crack is presented. This method uses the extended isogeometric analysis (XIGA) based on PHT-splines (Polynomial splines over Hierarchical T-meshes), which is abbreviated as XIGA-PHT. In XIGA-PHT, the isogeometric displacement approximation is locally enriched with enrichment functions, which efficiently capture the displacement discontinuity across the crack face as well as the stress singularity in the vicinity of the crack tip. On the one hand, the rotational degrees of freedom (RDOFs) are not required in Kirchhoff–Love theory, which drastically reduces the complexity of enrichment mode and computational scale for crack analysis. On the other hand, the PHT-splines basis functions can automatically satisfy the requirement of C¹-continuity for the Kirchhoff–Love theory. Moreover, the PHT-splines facilitate the local refinement, which is the deficiency of NURBS-based isogeometric formulations. The local refinement is highly suitable for adaptive analysis. The stress recovery-based posteriori error estimator combined with the superconvergent patch recovery (SPR) technique is used to evaluate the approximate local discretization error. A new strategy for selecting enriched recovered functions in the enriched areas was proposed. Special functions extracted from the asymptotic stress solutions are applied to obtain the recovered stress field in the enriched area. The results of stress intensity factors or J-integral values obtained by the adaptive XIGA-PHT are compared with reference solutions. Several thin plate and shell illustrative examples demonstrate the effectiveness and accuracy of the proposed adaptive XIGA-PHT.     

An <Emphasis Type="Italic">h</Emphasis>-adaptive RKDG method with troubled-cell indicator for one-dimensional detonation wave simulations

In this work, we discuss an extension of the adaptive technique in Zhu and Qiu (J. Comput. Phys. 228, 6957-6976 2009) to design an h-adaptive Runge-Kutta discontinuous Galerkin (RKDG) method for the simulations of several classical one-dimensional detonation waves. The TVB troubled-cell indicator is employed to detect the troubled cells which are believed to contain the discontinuities. An adaptive mesh is generated at each time-level by refining the troubled cells and coarsening the others. A recursive multi-level mesh refinement technique is designed to avoid the problem that the detonation front moves so fast that there are not enough cells to resolve the detonation front before it leaves. We describe the numerical implementation in detail including the adaptive procedure, solution reconstruction method and troubled-cell indicator. Furthermore, a high order positivity-preserving technique is employed for the robustness of our algorithm. Extensive numerical tests are conducted to show the effectiveness of the adaptive strategy and advantages of our adaptive method over the fixed-mesh RKDG method in saving the computational storage and improving the solution quality.     

Four-triangles adaptive algorithms for RTIN terrain meshes

We present a refinement and coarsening algorithm for the adaptive representation of Right-Triangulated Irregular Network (RTIN) meshes. The refinement algorithm is very simple and proceeds uniformly or locally in triangle meshes. The coarsening algorithm decreases mesh complexity by reducing unnecessary data points in the mesh after a given error criterion is applied. We describe the most important features of the algorithms and give a brief numerical study on the propagation associated with the adaptive scheme used for the refinement algorithm. We also present a comparison with a commercial tool for mesh simplification, Rational Reducer, showing that our coarsening algorithm offers better results in terms of accuracy of the generated meshes.     

Embeddings on a boolean cube

In this paper, we characterize a class of graphs which can be embedded on a boolean cube. Some of the graphs in this class are identified with the well known graphs such asmulti-dimensional mesh of trees, tree of meshes, etc. We suggest (i) an embedding of anr-dimensional mesh of trees ofn ^r (r+1)–rn ^r–1 nodes on a boolean cube of (2n) ^r nodes, and (ii) an embedding of a tree of meshes with 2n ² logn+n ² nodes on a boolean cube withn ² exp₂ (log (2 logn+1)]) nodes.     

Numerical evaluation of finite Fourier integrals

A computationally efficient algorithm for evaluating Fourier integrals ∫¹_?1?(x)e^iωxdx using interpolatory quadrature formulas on any set of collocation points is presented. Examples are given to illustrate the performances of interpolatory formulas which are based on the applications of the Fejér, Clenshaw—Curtis, Basu and the Newton—Cotes points. Initially, the formulas for nonoscillatory integrals are generated and then generalizations to finite Fourier integrals are made. Extensions of this algorithm to some other weighted integrals are also considered.     

Particle methods for stochastic optimal control problems

When dealing with numerical solution of stochastic optimal control problems, stochastic dynamic programming is the natural framework. In order to try to overcome the so-called curse of dimensionality, the stochastic programming school promoted another approach based on scenario trees which can be seen as the combination of Monte Carlo sampling ideas on the one hand, and of a heuristic technique to handle causality (or nonanticipativeness) constraints on the other hand. However, if one considers that the solution of a stochastic optimal control problem is a feedback law which relates control to state variables, the numerical resolution of the optimization problem over a scenario tree should be completed by a feedback synthesis stage in which, at each time step of the scenario tree, control values at nodes are plotted against corresponding state values to provide a first discrete shape of this feedback law from which a continuous function can be finally inferred. From this point of view, the scenario tree approach faces an important difficulty: at the first time stages (close to the tree root), there are a few nodes (or Monte-Carlo particles), and therefore a relatively scarce amount of information to guess a feedback law, but this information is generally of a good quality (that is, viewed as a set of control value estimates for some particular state values, it has a small variance because the future of those nodes is rich enough); on the contrary, at the final time stages (near the tree leaves), the number of nodes increases but the variance gets large because the future of each node gets poor (and sometimes even deterministic). After this dilemma has been confirmed by numerical experiments, we have tried to derive new variational approaches. First of all, two different formulations of the essential constraint of nonanticipativeness are considered: one is called algebraic and the other one is called functional. Next, in both settings, we obtain optimality conditions for the corresponding optimal control problem. For the numerical resolution of those optimality conditions, an adaptive mesh discretization method is used in the state space in order to provide information for feedback synthesis. This mesh is naturally derived from a bunch of sample noise trajectories which need not to be put into the form of a tree prior to numerical resolution. In particular, an important consequence of this discrepancy with the scenario tree approach is that the same number of nodes (or points) are available from the beginning to the end of the time horizon. And this will be obtained without sacrifying the quality of the results (that is, the variance of the estimates). Results of experiments with a hydro-electric dam production management problem will be presented and will demonstrate the claimed improvements. A more realistic problem will also be presented in order to demonstrate the effectiveness of the method for high dimensional problems.     

A matrix-based measure of inter-node walk relatedness in a network

For a pair of nodes in a network, a measure of walk relatedness is introduced. The measure is based on the total weight (number) of k-step walks connecting the pair, i.e., the corresponding entry of the kth power of the network matrix as k → ∞. The damping factor r ^?k is used, where r is the largest eigenvalue of the network matrix. The measure turns out to be equal to the product of the pair’s coreness values, i.e., the nodes’ coordinates in the network matrix’s right and left eigenvectors corresponding to r. The reduction of walk relatedness in a network caused by the removal of a node or link is investigated, i.e., the dependence of the reduction on the structural position (coreness) of the removed element. It is revealed that the “damage” can be measured by the drop in the value of r after the removal; to find this drop, the perturbation method is used. Some possible applications are indicated, and a numerical example with a large real network of 197 nodes and 780 links is considered.     

Uniform grid approximation of nonsmooth solutions with improved convergence for a singularly perturbed convection-diffusion equation with characteristic layers

A mixed boundary value problem for a singularly perturbed elliptic convection-diffusion equation with constant coefficients in a square domain is considered. Dirichlet conditions are specified on two sides orthogonal to the flow, and Neumann conditions are set on the other two sides. The right-hand side and the boundary functions are assumed to be sufficiently smooth, which ensures the required smoothness of the desired solution in the domain, except for neighborhoods of the corner points. Only zero-order compatibility conditions are assumed to hold at the corner points. The problem is solved numerically by applying an inhomogeneous monotone difference scheme on a rectangular piecewise uniform Shishkin mesh. The inhomogeneity of the scheme lies in that the approximating difference equations are not identical at different grid nodes but depend on the perturbation parameter. Under the assumptions made, the numerical solution is proved to converge ?-uniformly to the exact solution in a discrete uniform metric at an O(N ^?3/2ln² N) rate, where N is the number of grid nodes in each coordinate direction.     

Uniform grid approximation of nonsmooth solutions to the mixed boundary value problem for a singularly perturbed reaction-diffusion equation in a rectangle

A mixed boundary value problem for a singularly perturbed reaction-diffusion equation in a square is considered. A Neumann condition is specified on one side of the square, and a Dirichlet condition is set on the other three. It is assumed that the coefficient of the equation, its right-hand side, and the boundary values of the desired solution or its normal derivative on the sides of the square are smooth enough to ensure the required smoothness of the solution in a closed domain outside the neighborhoods of the corner points. No compatibility conditions are assumed to hold at the corner points. Under these assumptions, the desired solution in the entire closed domain is of limited smoothness: it belongs only to the Hölder class C ^μ, where μ ∈ (0, 1) is arbitrary. In the domain, a nonuniform rectangular mesh is introduced that is refined in the boundary domain and depends on a small parameter. The numerical solution to the problem is based on the classical five-point approximation of the equation and a four-point approximation of the Neumann boundary condition. A mesh refinement rule is described under which the approximate solution converges to the exact one uniformly with respect to the small parameter in the L _∞ ^h norm. The convergence rate is O(N ^?2ln² N), where N is the number of mesh nodes in each coordinate direction. The parameter-uniform convergence of difference schemes for mixed problems without compatibility conditions at corner points was not previously analyzed.     

Convergence of an adaptive Ka?anov FEM for quasi-linear problems

We design an adaptive finite element method to approximate the solutions of quasi-linear elliptic problems. The algorithm is based on a Ka?anov iteration and a mesh adaptation step is performed after each linear solve. The method is thus inexact because we do not solve the discrete nonlinear problems exactly, but rather perform one iteration of a fixed point method (Ka?anov), using the approximation of the previous mesh as an initial guess. The convergence of the method is proved for any reasonable marking strategy and starting from any initial mesh. We conclude with some numerical experiments that illustrate the theory.     

The bi-objective Pollution-Routing Problem

The bi-objective Pollution-Routing Problem is an extension of the Pollution-Routing Problem (PRP) which consists of routing a number of vehicles to serve a set of customers, and determining their speed on each route segment. The two objective functions pertaining to minimization of fuel consumption and driving time are conflicting and are thus considered separately. This paper presents an adaptive large neighborhood search algorithm (ALNS), combined with a speed optimization procedure, to solve the bi-objective PRP. Using the ALNS as the search engine, four a posteriori methods, namely the weighting method, the weighting method with normalization, the epsilon-constraint method and a new hybrid method (HM), are tested using a scalarization of the two objective functions. The HM combines adaptive weighting with the epsilon-constraint method. To evaluate the effectiveness of the algorithm, new sets of instances based on real geographic data are generated, and a library of bi-criteria PRP instances is compiled. Results of extensive computational experiments with the four methods are presented and compared with one another by means of the hypervolume and epsilon indicators. The results show that HM is highly effective in finding good-quality non-dominated solutions on PRP instances with 100 nodes.     

Cubic superconvergent finite volume element method for one-dimensional elliptic and parabolic equations

In this paper, a cubic superconvergent finite volume element method based on optimal stress points is presented for one-dimensional elliptic and parabolic equations. For elliptic problem, it is proved that the method has optimal third order accuracy with respect to H¹ norm and fourth order accuracy with respect to L² norm. We also obtain that the scheme has fourth order superconvergence for derivatives at optimal stress points. For parabolic problem, the scheme is given and error estimate is obtained with respect to L² norm. Finally, numerical examples are provided to show the effectiveness of the method.     

Gate points in continuous location between regions with different ?p norms

In this paper, a set of notable points is given from the ?_p-distance between a point P and a straight line r. The problem of the geodesic path between two points of R² separated by a straight line r with different norms in each half-plane is then studied from the notable points of these points. This geodesic path provides a point in r, called the “Gate point”, which is studied by varying ?_p- and ?_q-distances, and the slope m of the straight line r. The analytical expression of the Gate point is given in some particular cases.     

The best quadrature based on given Hermite information for the Sobolev class KW r[a, b]

As usual, denote by KW ^r[a, b] the Sobolev class consisting of every function whose (r ? 1)th derivative is absolutely continuous on the interval [a, b] and rth derivative is bounded by K a.e. in [a, b]. For a function f ∈ KW ^r [a, b], its values and derivatives up to r ? 1 order at a set of nodes x are known. These values are said to be the given Hermite information. This work reports the results on the best quadrature based on the given Hermite information for the class KW ^r [a, b]. Existence and concrete construction issue of the best quadrature are settled down by a perfect spline interpolation. It turns out that the best quadrature depends on a system of algebraic equations satisfied by a set of free nodes of the interpolation perfect spline. From our another new result, it is shown that the system can be converted in a closed form to two single-variable polynomial equations, each being of degree approximately r/2. As a by-product, the best interpolation formula for the class KW ^r [a, b] is also obtained.