Unconditional and optimal <Emphasis Type="Bold">H</Emphasis><Superscript>2</Superscript>-error estimates of two linear and conservative finite difference schemes for the Klein-Gordon-Schrödinger equation in high dimensions

The focus of this paper is on the optimal error bounds of two finite difference schemes for solving the d-dimensional (d = 2, 3) nonlinear Klein-Gordon-Schrödinger (KGS) equations. The proposed finite difference schemes not only conserve the mass and energy in the discrete level but also are efficient in practical computation because only two linear systems need to be solved at each time step. Besides the standard energy method, an induction argument as well as a ‘lifting’ technique are introduced to establish rigorously the optimal H ²-error estimates without any restrictions on the grid ratios, while the previous works either are not rigorous enough or often require certain restriction on the grid ratios. The convergence rates of the proposed schemes are proved to be at O(h ² + τ ²) with mesh-size h and time step τ in the discrete H ²-norm. The analysis method can be directly extended to other linear finite difference schemes for solving the KGS equations in high dimensions. Numerical results are reported to confirm the theoretical analysis for the proposed finite difference schemes.     

A prewavelet-based algorithm for the solution of second-order elliptic differential equations with variable coefficients on sparse grids

We present a Ritz-Galerkin discretization on sparse grids using prewavelets, which allows us to solve elliptic differential equations with variable coefficients for dimensions d ≥ 2. The method applies multilinear finite elements. We introduce an efficient algorithm for matrix vector multiplication using a Ritz-Galerkin discretization and semi-orthogonality. This algorithm is based on standard 1-dimensional restrictions and prolongations, a simple prewavelet stencil, and the classical operator-dependent stencil for multilinear finite elements. Numerical simulation results are presented for a three-dimensional problem on a curvilinear bounded domain and for a six-dimensional problem with variable coefficients. Simulation results show a convergence of the discretization according to the approximation properties of the finite element space. The condition number of the stiffness matrix can be bounded below 10 using a standard diagonal preconditioner.     

Two-scale sparse finite element approximations

To reduce computational cost,we study some two-scale finite element approximations on sparse grids for elliptic partial differential equations of second order in a general setting.Over any tensor product domain ?R~d with d = 2,3,we construct the two-scale finite element approximations for both boundary value and eigenvalue problems by using a Boolean sum of some existing finite element approximations on a coarse grid and some univariate fine grids and hence they are cheaper approximations.As applications,we obtain some new efficient finite element discretizations for the two classes of problem:The new two-scale finite element approximation on a sparse grid not only has the less degrees of freedom but also achieves a good accuracy of approximation.     

Multivariate exponential analysis from the minimal number of samples

The problem of multivariate exponential analysis or sparse interpolation has received a lot of attention, especially with respect to the number of samples required to solve it unambiguously. In this paper we show how to bring the number of samples down to the absolute minimum of (d +?1)n where d is the dimension of the problem and n is the number of exponential terms. To this end we present a fundamentally different approach for the multivariate problem statement. We combine a one-dimensional exponential analysis method such as ESPRIT, MUSIC, the matrix pencil or any Prony-like method, with some linear systems of equations because the multivariate exponents are inner products and thus linear expressions in the parameters.     

LIE SYMMETRY ANALYSIS AND PAINLEVE ANALYSIS OF THE NEW （2＋1）-DIMENSIONAL KdV EQUATION

Lie point symmetries associated with the new （2＋1）-dimensional KdV equation ut ＋ 3uxuy ＋ uxxy = 0 are investigated. Some similarity reductions are derived by solving the corresponding characteristic equations. Painlevé analysis for this equation is also presented and the soliton solution is obtained directly from the Bǎcklund transformation.     

Poisson brackets of mappings obtained as (<Emphasis Type="Italic">q</Emphasis>,−<Emphasis Type="Italic">p</Emphasis>) reductions of lattice equations

In this paper, we present Poisson brackets of certain classes of mappings obtained as general periodic reductions of integrable lattice equations. The Poisson brackets are derived from a Lagrangian, using the so-called Ostrogradsky transformation. The (q,?p) reductions are (p + q)-dimensional maps and explicit Poisson brackets for such reductions of the discrete KdV equation, the discrete Lotka–Volterra equation, and the discrete Liouville equation are included. Lax representations of these equations can be used to construct sufficiently many integrals for the reductions. As examples we show that the (3,?2) reductions of the integrable partial difference equations are Liouville integrable in their own right.     

An unconditionally stable spatial sixth-order CCD-ADI method for the two-dimensional linear telegraph equation

The telegraph equation is one of the important models in many physics and engineering. In this work, we discuss the high-order compact finite difference method for solving the two-dimensional second-order linear hyperbolic equation. By using a combined compact finite difference method for the spatial discretization, a high-order alternating direction implicit method (ADI) is proposed. The method is O(τ² + h⁶) accurate, where τ, h are the temporal step size and spatial size, respectively. Von Neumann linear stability analysis shows that the method is unconditionally stable. Finally, numerical examples are used to illustrate the high accuracy of the new difference scheme.     

A fast numerical method for block lower triangular Toeplitz with dense Toeplitz blocks system with applications to time-space fractional diffusion equations

Based on the circulant-and-skew-circulant representation of Toeplitz matrix inversion and the divide-and-conquer technique, a fast numerical method is developed for solving N-by-N block lower triangular Toeplitz with M-by-M dense Toeplitz blocks system with \(\mathcal {O}(MN\log N(\log N+\log M))\) complexity and \(\mathcal {O}(NM)\) storage. Moreover, the method is employed for solving the linear system that arises from compact finite difference scheme for time-space fractional diffusion equations with significant speedup. Numerical examples are given to show the efficiency of the proposed method.     

Instance Optimality of the Adaptive Maximum Strategy

In this paper, we prove that the standard adaptive finite element method with a (modified) maximum marking strategy is instance optimal for the total error, being the square root of the squared energy error plus the squared oscillation. This result will be derived in the model setting of Poisson’s equation on a polygon, linear finite elements, and conforming triangulations created by newest vertex bisection.     

Parametric Integer Programming Analysis: A Contraction Approach

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region.     

On expansion and topological overlap

We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map \(X\rightarrow \mathbb {R}^d\) there exists a point \(p\in \mathbb {R}^d\) that is contained in the images of a positive fraction \(\mu >0\) of the d-cells of X. More generally, the conclusion holds if \(\mathbb {R}^d\) is replaced by any d-dimensional piecewise-linear manifold M, with a constant \(\mu \) that depends only on d and on the expansion properties of X, but not on M.     

Solution method for boundary value problems for ordinary differential equations on complexes (Graphs)

For second-order ordinary differential equations in a domain that is a finite set of intersecting segments of the axis O _x , we consider problems with local and nonlocal boundary conditions. A system of intersecting segments is referred to as a complex, whose topological structure is described by a graph. For the integration of differential equations, we suggest an exact difference scheme, which reduces the solution of the problem to a system of second-order difference equations on the segments of the complex with boundary conditions and matching conditions at the graph vertices. Depending on the topological structure of the graph, we consider two algorithms for solving systems of linear algebraic equations. A detailed justification of the method is presented.     

On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

Galerkin finite element method and error analysis for the fractional cable equation

The cable equation is one of the most fundamental equations for modeling neuronal dynamics. These equations can be derived from the Nernst-Planck equation for electro-diffusion in smooth homogeneous cylinders. Fractional cable equations are introduced to model electrotonic properties of spiny neuronal dendrites. In this paper, a Galerkin finite element method(GFEM) is presented for the numerical simulation of the fractional cable equation(FCE) involving two integro-differential operators. The proposed method is based on a semi-discrete finite difference approximation in time and Galerkin finite element method in space. We prove that the numerical solution converges to the exact solution with order O(τ+h^l+1) for the lth-order finite element method. Further, a novel Galerkin finite element approximation for improving the order of convergence is also proposed. Finally, some numerical results are given to demonstrate the theoretical analysis. The results show that the numerical solution obtained by the improved Galerkin finite element approximation converges to the exact solution with order O(τ²+h^l+1).     

Approximation of systems of singularly perturbed elliptic reaction-diffusion equations with two parameters

In a rectangle, the Dirichlet problem for a system of two singularly perturbed elliptic reaction-diffusion equations is considered. The higher order derivatives of the ith equation are multiplied by the perturbation parameter ? _i ² (i = 1, 2). The parameters ?_i take arbitrary values in the half-open interval (0, 1]. When the vector parameter ? = (?₁, ?₂) vanishes, the system of elliptic equations degenerates into a system of algebraic equations. When the components ?₁ and (or) ?₂ tend to zero, a double boundary layer with the characteristic width ?₁ and ?₂ appears in the vicinity of the boundary. Using the grid refinement technique and the classical finite difference approximations of the boundary value problem, special difference schemes that converge ?-uniformly at the rate of O(N ^?2ln² N) are constructed, where N = min N _s, N _s + 1 is the number of mesh points on the axis x _s.     

Complex vector measure and integral over manifolds with locally finite variations

It is well known that any compactly supported continuous complex differential n-form can be integrated over real n-dimensional C¹ manifolds in C^m (m ≥ n). For n = 1, the integral along any locally rectifiable curve is defined. Another generalization is the theory of currents (linear functionals on the space of compactly supported C^∞ differential forms). The topic of the article is the integration of measurable complex differential (n, 0)-forms (containing no \(d{\bar z_j}\)) over real n-dimensional C⁰ manifolds in C^m with locally finite n-dimensional variations (a generalization of locally rectifiable curves to dimensions n > 1). The last result is that a real n-dimensional manifold C¹ embedded in C^m has locally finite variations, and the integral of a measurable complex differential (n, 0)-form defined in the article can be calculated by a well-known formula.     

On sets of directions determined by subsets of ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

Given E ? ? ^d , d ≥ 2, define

$D(E) \equiv \left\{ {{{x - y} \over {\left| {x - y} \right|}}:x,y \in E} \right\} \subset {S^{d - 1}}$

to be the set of directions determined by E. We prove that if the Hausdorff dimension of E is greater than d ? 1, then σ(D(E)) > 0, where σ denotes the surface measure on S ^d?1. In the process, we prove some tight upper and lower bounds for the maximal function associated with the Radon-Nikodym derivative of the natural measure on D. This result is sharp, since the conclusion fails to hold if E is a (d ? 1)-dimensional hyper-plane. This result can be viewed as a continuous analog of a recent result of Pach, Pinchasi, and Sharir ([22, 23]) on directions determined by finite subsets of ? ^d . We also discuss the case when the Hausdorff dimension of E is precisely d ? 1, where some interesting counter-examples have been obtained by Simon and Solomyak ([25]) in the planar case. In response to the conjecture stated in this paper, T. Orponen and T. Sahlsten ([20]) have recently proved that if the Hausdorff dimension of E equals d ? 1 and E is rectifiable and is not contained in a hyper-pane, the Lebesgue measure of the set of directions is still positive. Finally, we show that our continuous results can be used to recover and, in some cases, improve the exponents for the corresponding results in the discrete setting for large classes of finite point sets. In particular, we prove that a finite point set P ? ? ^d , d ≥ 3, satisfying a certain discrete energy condition (Definition 3.1) determines ? #P distinct directions.

     

On the complexity of the family of convex sets in ℝ<Superscript> <Emphasis Type="Italic">d</Emphasis> </Superscript>

Estimates of quantities characterizing the complexity of the family of convex subsets of the d-dimensional cube [1, n]^d as n→∞ are given. The geometric properties of spaces with norm generated by the generalized majorant of partial sums are studied.     

Weak-type Estimates and Potential Estimates for Elliptic Equations with Drift Terms

We consider divergence form elliptic equations with a strongly singular drift term ?d i v(A?u)+b??u=μ in a domain \({\Omega } \subset \mathbb {R}^{n}\) (n≥3). We give a weak-type \(L^{1} - L^{n / (n - 2), \infty }\) estimate for a solution to the Dirichlet problem with homogeneous boundary condition. Moreover, we give a two-sided pointwise potential estimate for a weak solution and its applications.     

Exact soliton solutions of a D-dimensional nonlinear Schrödinger equation with damping and diffusive terms

In the present study, we apply function transformation methods to the D-dimensional nonlinear Schrödinger (NLS) equation with damping and diffusive terms. As special cases, this method applies to the sine-Gordon, sinh-Gordon, and other equations. Also, the results show that these equations depend on only one function that can be obtained analytically by solving an ordinary differential equation. Furthermore, certain exact solutions of these three equations are shown to lead to the exact soliton solutions of a D-dimensional NLS equation with damping and diffusive terms. Finally, our results imply that the planar solitons, N multiple solitons, propagational breathers, and quadric solitons are solutions to the sine-Gordon, sinh-Gordon, and D-dimensional NLS equations.