Higher-order polynomial approximation

A new approach to polynomial higher-order approximation (smoothing) based on the basic elements method (BEM) is proposed. A BEM polynomial of degree n is defined by four basic elements specified on a three-point grid: x ₀ + α < x ₀ < x ₀ + β, αβ <0. Formulas for the calculation of coefficients of the polynomial model of order 12 were derived. These formulas depend on the interval length, continuous parameters α and β, and the values of f ^(m)(x ₀+ν), ν = α, β, 0, m = 0,3. The application of higher-degree BEM polynomials in piecewise-polynomial approximation and smoothing improves the stability and accuracy of calculations when the grid step is increased and reduces the computational complexity of the algorithms.     

Compact difference method for solving the fractional reaction–subdiffusion equation with Neumann boundary value condition

In this paper, we derive a high-order compact finite difference scheme for solving the reaction–subdiffusion equation with Neumann boundary value condition. The L1 method is used to approximate the temporal Caputo derivative, and the compact difference operator is applied for spatial discretization. We prove that the compact finite difference method is unconditionally stable and convergent with order O(τ^2?α+h⁴) in L₂ norm, where τ, α, and h are the temporal step size, the order of time fractional derivative and the spatial step size, respectively. Finally, some numerical experiments are carried out to show the effectiveness of the proposed difference scheme.     

On Approximating Polygonal Curves in Two and Three Dimensions

Given a polygonal curve P =[p₁, p₂, . . . , p_n], the polygonal approximation problem considered calls for determining a new curve P′ = [p′₁, p′₂, . . . , p′_m] such that (i) m is significantly smaller than n, (ii) the vertices of P′ are an ordered subset of the vertices of P, and (iii) any line segment [p′_A, p′_{A + 1} of P′ that substitutes a chain [p_B, . . . , p_C] in P is such that for all i where B ≤ i ≤ C, the approximation error of p_i with respect to [p′_A, p′_{A + 1}], according to some specified criterion and metric, is less than a predetermined error tolerance. Using the parallel-strip error criterion, we study the following problems for a curve P in R^d, where d = 2, 3: (i) minimize m for a given error tolerance and (ii) given m, find the curve P′ that has the minimum approximation error over all curves that have at most m vertices. These problems are called the min-# and min-ϵ problems, respectively. For R² and with any one of the L₁, L₂, or L_∞ distance metrics, we give algorithms to solve the min-# problem in O(n²) time and the min-ϵ problem in O(n² log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R³ that is strictly monotone with respect to one of the three axes, we show that if the L₁ and L_∞ metrics are used then the min-# problem can be solved in O(n²) time and the min-ϵ problem can be solved in O(n³) time. If distances are computed using the L₂ metric then the min-# and min-ϵ problems can be solved in O(n³) and O(n³ log n) time, respectively. All of our algorithms exhibit O(n²) space complexity. Finally, we show that if it is not essential to minimize m, simple modifications of our algorithms afford a reduction by a factor of n for both time and space.     

Lp(R0) (p ⩾ 1) stability in the mean m (m ⩾ 1) of a class of stochastic volterra integral equations

In this paper we consider a class of stochastic nonlinear Volterra integral equation. The problem of L^P(R₀ (p ? 1) stability in the mean m (m ? 1) is examined.In Section 2, the random Banach fixed-point theorem is used to establish the existence and uniqueness of solutions of the system in some general Banach spaces. These results are then used to study the L^P(R₀) (p ? 1) stability in the mean m (m ? 1) of the system.For illustration, an example of the visually induced height orientation of the fly (Musca domestica) is considered.     

Numerical stability of incompletely integrated shape functions

Finite element stiffness matrices formed by “unstable” integration schemes regain positive definiteness with a sufficient number of imposed boundary conditions. Moreover, the feared decline in the condition of these matrices does not materialize; their spectral condition number being O(h^?2m) as for the strictly variational elements.     

Geometric pattern matching for point sets in the plane under similarity transformations

We consider the following geometric pattern matching problem: Given two sets of points in the plane, P and Q, and some (arbitrary) δ>0, find a similarity transformation T (translation, rotation and scale) such that h(T(P),Q)<δ, where h(⋅,⋅) is the directional Hausdorff distance with L_∞ as the underlying metric; or report that none exists. We are only interested in the decision problem, not in minimizing the Hausdorff distance, since in the real world, where our applications come from, δ is determined by the practical uncertainty in the position of the points (pixels). Similarity transformations have not been dealt with in the context of the Hausdorff distance and we fill the gap here. We present efficient algorithms for this problem imposing a reasonable separation restriction on the points in the set Q. If the L_∞ distance between every pair of points in Q is at least 8δ, then the problem can be solved in O(mn²logn) time, where m and n are the numbers of points in P and Q respectively. If the L_∞ distance between every pair of points in Q is at least cδ, for some c, 0<c<1, we present a randomized approximate solution with expected runtime O(n²c−4ε−8log⁴mn), where ε>0 controls the approximation. Our approximation is on the size of the subset, B⊆P, such that h(T(B),Q)<δ and |B|>(1−ε)|P| with high probability.     

An algorithm for Exact Satisfiability analysed with the number of clauses as parameter

We give an algorithm for Exact Satisfiability with polynomial space usage and a time bound of poly(L)⋅m!, where m is the number of clauses and L is the length of the formula. Skjernaa has given an algorithm for Exact Satisfiability with time bound poly(L)⋅m² but using exponential space. We leave the following problem open: Is there an algorithm for Exact Satisfiability using only polynomial space with a time bound of cm, where c is a constant and m is the number of clauses?     

A proof of the Gilbert-Pollak conjecture on the Steiner ratio

LetP be a set ofn points on the euclidean plane. LetL _s(P) andL _m (P) denote the lengths of the Steiner minimum tree and the minimum spanning tree onP, respectively. In 1968, Gilbert and Pollak conjectured that for anyP,L _s (P)≥(√3/2)L _m (P). We provide a proof for their conjecture in this paper.     

A posteriori error estimation for discontinuous Galerkin solutions of hyperbolic problems

We analyze the spatial discretization errors associated with solutions of one-dimensional hyperbolic conservation laws by discontinuous Galerkin methods (DGMs) in space. We show that the leading term of the spatial discretization error with piecewise polynomial approximations of degree p is proportional to a Radau polynomial of degree p+1 on each element. We also prove that the local and global discretization errors are O(Δx^2(p+1)) and O(Δx^2p+1) at the downwind point of each element. This strong superconvergence enables us to show that local and global discretization errors converge as O(Δx^p+2) at the remaining roots of Radau polynomial of degree p+1 on each element. Convergence of local and global discretization errors to the Radau polynomial of degree p+1 also holds for smooth solutions as p→∞. These results are used to construct asymptotically correct a posteriori estimates of spatial discretization errors that are effective for linear and nonlinear conservation laws in regions where solutions are smooth.     

Fast computation of smallest enclosing circle with center on a query line segment

Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p₁,p₂,…,pn} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765-776] have proposed an algorithm that solves the query problem in O(log²n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n²).     

Discretization of elliptic differential equations on curvilinear bounded domains with sparse grids

Elliptic differential equations can be discretized with bilinear finite elements. Using sparse grids instead of full grids, the dimension of the finite element space for the 2D problem reduces fromO(N ²) toO (N logN) while the approximation properties are nearly the same for smooth functions. A method is presented which discretizes elliptic differential equations on curvilinear bounded domains with adaptive sparse grids. The grid is generated by a transformation of the domain. This method has the same behaviour of convergence like the sparse grid discretization on the unit square.     

Optimal maximum norm error estimates for some finite element methods for treating the Dirichlet problem

The goal of this paper is to establish optimalL ^∞ error estimates for a few different finite element type methods for the Dirichlet problem in a bounded domain. The methods are selected so as to avoid the necessity for imposing boundary conditions on the trial functions, usually difficult in practice. Three specific methods are treated. These are the method of interpolated boundary condition and two methods of Nitsche.     

Quasi-optimal upper bounds for simplex range searching and new zone theorems

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ?^d so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n <m <n ^d ), then we show that it is possible to answer any query inO(n ^1+?/m ^1/d ) query time afterO(m ^1+?) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n ^d+?) storage for any fixed ? > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.     

P 1-Nonconforming Quadrilateral Finite Volume Methods for the Semilinear Elliptic Equations

In this paper we use P ₁-nonconforming quadrilateral finite volume methods with interpolated coefficients to solve the semilinear elliptic problems. Two types of control volumes are applied. Optimal error estimates in H ¹-norm on the quadrilateral mesh and superconvergence of derivative on the rectangular mesh are derived by using the continuity argument, respectively. In addition, numerical experiments are presented adequately to confirm the theoretical analysis and optimal error estimates in L ²-norm is also observed obviously. Compared with the standard Q ₁-conforming quadrilateral element, numerical results of the proposed finite volume methods show its better performance than others.     

Discontinuous Galerkin Method for Linear Free-Surface Gravity Waves

In this paper, we discuss a discontinuous Galerkin finite (DG) element method for linear free surface gravity waves. We prove that the algorithm is unconditionally stable and does not require additional smoothing or artificial viscosity terms in the free surface boundary condition to prevent numerical instabilities on a non-uniform mesh. A detailed error analysis of the full time-dependent algorithm is given, showing that the error in the wave height and velocity potential in the L²-norm is in both cases of optimal order and proportional to O(Δt²+h^p+1), without the need for a separate velocity reconstruction, with p the polynomial order, h the mesh size and Δt the time step. The error analysis is confirmed with numerical simulations. In addition, a Fourier analysis of the fully discrete scheme is conducted which shows the dependence of the frequency error and wave dissipation on the time step and mesh size. The algebraic equations for the DG discretization are derived in a way suitable for an unstructured mesh and result in a symmetric positive definite linear system. The algorithm is demonstrated on a number of model problems, including a wave maker, for discretizations with accuracy ranging from second to fourth order.This revised version was published online in July 2005 with corrected volume and issue numbers.     

Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial

The reliability polynomial of a graph counts its connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph’s reliability polynomial. We develop an improved SIS algorithm for estimating the reliability polynomial. The new algorithm runs in expected time O(mlogn α(m,n)) at worst and ≈m in practice, compared to Θ(m ²) for the previous algorithm. We analyze the error bounds of this algorithm, including comparison to alternative estimation algorithms. In addition to the theoretical analysis, we discuss methods for estimating the variance and describe experimental results on a variety of random graphs.     

On Steiner minimal trees withL p distance

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ ?x ₂¦ ^p + ¦y₁ ?y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < ∞, each Steiner point is of degree exactly three. Define the Steiner ratio ? _p to be inf{L _s (P)/L _m (P)¦P?L _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ?₁ = 2/3. Chung and Graham proved ?₂ > 0.842. We prove in this paper that ?{∞} = 2/3 and √(√2/2)?₁?₂ ≤ ?_p ≤ √3/2 for anyp.     

A polynomial newton method for linear programming

An algorithm is presented for solving a set of linear equations on the nonnegative orthant. This problem can be made equivalent to the maximization of a simple concave function subject to a similar set of linear equations and bounds on the variables. A Newton method can then be used which enforces a uniform lower bound which increases geometrically with the number of iterations. The basic steps are a projection operation and a simple line search. It is shown that this procedure either proves in at mostO(n ² m ² L) operations that there is no solution or, else, computes an exact solution in at mostO(n ³ m ² L) operations. The linear programming problem is treated as a parametrized feasibility problem and solved in at mostO(n ³ m ² L) operations.     

The simulation of 3D elastic scattering produced by thin rigid inclusions using the traction boundary element method

A mixed formulation that uses both the traction boundary element method (TBEM) and the boundary element method (BEM) is proposed to compute the three-dimensional (3D) propagation of elastic waves scattered by two-dimensional (2D) thin rigid inclusions. Although the conventional direct BEM has limitations when dealing with thin-body problems, this model overcomes that difficulty. It is formulated in the frequency domain and, taking into account the 2-1/2D configuration of the problem, can be expressed in terms of waves with varying wavenumbers in the zdirection, k_z. The elastic medium is homogeneous and unbounded and it should be noted that no restrictions are imposed on the geometry and orientation of the internal crack.