A posteriori discontinuous finite element error estimation for two-dimensional hyperbolic problems

We analyze the discontinuous finite element errors associated with p-degree solutions for two-dimensional first-order hyperbolic problems. We show that the error on each element can be split into a dominant and less dominant component and that the leading part is O(h^p+1) and is spanned by two (p+1)-degree Radau polynomials in the x and y directions, respectively. We show that the p-degree discontinuous finite element solution is superconvergent at Radau points obtained as a tensor product of the roots of (p+1)-degree Radau polynomial. For a linear model problem, the p-degree discontinuous Galerkin solution flux exhibits a strong O(h^2p+2) local superconvergence on average at the element outflow boundary. We further establish an O(h^2p+1) global superconvergence for the solution flux at the outflow boundary of the domain. These results are used to construct simple, efficient and asymptotically correct a posteriori finite element error estimates for multi-dimensional first-order hyperbolic problems in regions where solutions are smooth.     

Superconvergence of Discontinuous Finite Element Solutions for Transient Convection–diffusion Problems

We present a study of the local discontinuous Galerkin method for transient convection–diffusion problems in one dimension. We show that p-degree piecewise polynomial discontinuous finite element solutions of convection-dominated problems are O(Δx ^p+2) superconvergent at Radau points. For diffusion- dominated problems, the solution’s derivative is O(Δx ^p+2) superconvergent at the roots of the derivative of Radau polynomial of degree p+1. Using these results, we construct several asymptotically exact a posteriori finite element error estimates. Computational results reveal that the error estimates are asymptotically exact.This revised version was published online in July 2005 with corrected volume and issue numbers.     

Superconvergence of Discontinuous Galerkin Methods for Convection-Diffusion Problems

Some discontinuous Galerkin methods for the linear convection-diffusion equation −ε u″+bu′=f are studied. Based on superconvergence properties of numerical fluxes at element nodes established in some earlier works, e.g., Celiker and Cockburn in Math. Comput. 76(257), 67–96, 2007, we identify superconvergence points for the approximations of u or q=u′. Our results are twofold: 1) For the minimal dissipation LDG method (we call it md-LDG in this paper) using polynomials of degree p, we prove that the leading terms of the discretization errors for u and q are proportional to the right Radau and left Radau polynomials of degree p+1, respectively. Consequently, the zeros of the right-Radau and left-Radau polynomials of degree p+1 are the superconvergence points of order p+2 for the discretization errors of the potential and of the gradient, respectively.     

Optimal Error Estimates for the Fully Discrete Interior Penalty DG Method for the Wave Equation

In Grote et al. (SIAM J. Numer. Anal., 44:2408–2431, 2006) a symmetric interior penalty discontinuous Galerkin (DG) method was presented for the time-dependent wave equation. In particular, optimal a-priori error bounds in the energy norm and the L ²-norm were derived for the semi-discrete formulation. Here the error analysis is extended to the fully discrete numerical scheme, when a centered second-order finite difference approximation (“leap-frog” scheme) is used for the time discretization. For sufficiently smooth solutions, the maximal error in the L ²-norm error over a finite time interval converges optimally as O(h ^p+1+Δt ²), where p denotes the polynomial degree, h the mesh size, and Δt the time step.     

Spatial and Modal Superconvergence of the Discontinuous Galerkin Method for Linear Equations

We apply the discontinuous Galerkin finite element method with a degree p polynomial basis to the linear advection equation and derive a PDE which the numerical solution solves exactly. We use a Fourier approach to derive polynomial solutions to this PDE and show that the polynomials are closely related to the \(\frac{p}{p+1}\) Padé approximant of the exponential function. We show that for a uniform mesh of N elements there exist \((p+1)N\) independent polynomial solutions, N of which can be viewed as physical and pN as non-physical. We show that the accumulation error of the physical mode is of order \(2p+1\). In contrast, the non-physical modes are damped out exponentially quickly. We use these results to present a simple proof of the superconvergence of the DG method on uniform grids as well as show a connection between spatial superconvergence and the superaccuracies in dissipation and dispersion errors of the scheme. Finally, we show that for a class of initial projections on a uniform mesh, the superconvergent points of the numerical error tend exponentially quickly towards the downwind based Radau points.     

Improvement of the accuracy in boundary element method based on high-order discretization

The boundary element method (BEM) is a popular method to solve various problems in engineering and physics and has been used widely in the last two decades. In high-order discretization the boundary elements are interpolated with some polynomial functions. These polynomials are employed to provide higher degrees of continuity for the geometry of boundary elements, and also they are used as interpolation functions for the variables located on the boundary elements. The main aim of this paper is to improve the accuracy of the high-order discretization in the two-dimensional BEM. In the high-order discretization, both the geometry and the variables of the boundary elements are interpolated with the polynomial function P_m, where m denotes the degree of the polynomial. In the current paper we will prove that if the geometry of the boundary elements is interpolated with the polynomial function P_m+1 instead of P_m, the accuracy of the results increases significantly. The analytical results presented in this work show that employing the new approach, the order of convergence increases from O(L₀)^m to O(L₀)^m+1 without using more CPU time where L₀ is the length of the longest boundary element. The theoretical results are also confirmed by some numerical experiments.     

The Local Discontinuous Galerkin Method for the Fourth-Order Euler–Bernoulli Partial Differential Equation in One Space Dimension. Part II: A Posteriori Error Estimation

In this paper new a posteriori error estimates for the local discontinuous Galerkin (LDG) method for one-dimensional fourth-order Euler–Bernoulli partial differential equation are presented and analyzed. These error estimates are computationally simple and are obtained by solving a local steady problem with no boundary condition on each element. We use the optimal error estimates and the superconvergence results proved in Part I to show that the significant parts of the discretization errors for the LDG solution and its spatial derivatives (up to third order) are proportional to \((k+1)\) -degree Radau polynomials, when polynomials of total degree not exceeding \(k\) are used. These results allow us to prove that the \(k\) -degree LDG solution and its derivatives are \(\mathcal O (h^{k+3/2})\) superconvergent at the roots of \((k+1)\) -degree Radau polynomials. We use these results to construct asymptotically exact a posteriori error estimates. We further apply the results proved in Part I to prove that, for smooth solutions, these a posteriori LDG error estimates for the solution and its spatial derivatives at a fixed time \(t\) converge to the true errors at \(\mathcal O (h^{k+5/4})\) rate. We also prove that the global effectivity indices, for the solution and its derivatives up to third order, in the \(L^2\) -norm converge to unity at \(\mathcal O (h^{1/2})\) rate. Our proofs are valid for arbitrary regular meshes and for \(P^k\) polynomials with \(k\ge 1\) , and for periodic and other classical mixed boundary conditions. Our computational results indicate that the observed numerical convergence rates are higher than the theoretical rates. Finally, we present a local adaptive procedure that makes use of our local a posteriori error estimate.     

Superconvergence of Local Discontinuous Galerkin Methods for Partial Differential Equations with Higher Order Derivatives

In this paper, we present a unified approach to study superconvergence behavior of the local discontinuous Galerkin (LDG) method for high-order time-dependent partial differential equations. We select the third and fourth order equations as our models to demonstrate this approach and the main idea. Superconvergence results for the solution itself and the auxiliary variables are established. To be more precise, we first prove that, for any polynomial of degree k, the errors of numerical fluxes at nodes and for the cell averages are superconvergent under some suitable initial discretization, with an order of \(O(h^{2k+1})\). We then prove that the LDG solution is \((k+2)\)-th order superconvergent towards a particular projection of the exact solution and the auxiliary variables. As byproducts, we obtain a \((k+1)\)-th and \((k+2)\)-th order superconvergence rate for the derivative and function value approximation separately at a class of Radau points. Moreover, for the auxiliary variables, we, for the first time, prove that the convergence rate of the derivative error at the interior Radau points can reach as high as \(k+2\). Numerical experiments demonstrate that most of our error estimates are optimal, i.e., the error bounds are sharp.     

Efficient bit-parallel multipliers over finite fields GF(2)

Hardware implementation of multiplication in finite field GF(2^m) based on sparse polynomials is found to be advantageous in terms of space-complexity as well as the time-complexity. In this paper, we present a new permutation method to construct the irreducible like-trinomials of the form (x + 1)^m + (x + 1)ⁿ + 1 for the implementation of efficient bit-parallel multipliers. For implementing the multiplications based on such polynomials, we have defined a like-polynomial basis (LPB) as an alternative to the original polynomial basis of GF(2^m). We have shown further that the modular arithmetic for the binary field based on like-trinomials is equivalent to the arithmetic for the field based on trinomials. In order to design multipliers for composite fields, we have found another permutation polynomial to convert irreducible polynomials into like-trinomials of the forms (x² + x + 1)^m + (x² + x + 1)ⁿ + 1, (x² + x)^m + (x² + x)ⁿ + 1 and (x⁴ + x + 1)^m + (x⁴ + x + 1)ⁿ + 1. The proposed bit-parallel multiplier over GF(2^4m) is found to offer a saving of about 33% multiplications and 42.8% additions over the corresponding existing architectures.     

A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

Applications of complete discrimination system for polynomial for classifications of traveling wave solutions to nonlinear differential equations

If a partial differential equation is reduced to an ordinary differential equation in the form u^′(ξ)=G(u,θ₁,…,θm) under the traveling wave transformation, where θ₁,…,θm are parameters, its solutions can be written as an integral form . Therefore, the key steps are to determine the parameters' scopes and to solve the corresponding integral. When G is related to a polynomial, a mathematical tool named complete discrimination system for polynomial is applied to this problem so that the parameter's scopes can be determined easily. The complete discrimination system for polynomial is a natural generalization of the discrimination △=b²−4ac of the second degree polynomial ax²+bx+c. For example, the complete discrimination system for the third degree polynomial F(w)=w³+d₂w²+d₁w+d₀ is given by and . In the paper, we give some new applications of the complete discrimination system for polynomial, that is, we give the classifications of traveling wave solutions to some nonlinear differential equations through solving the corresponding integrals. In finally, as a result, we give a partial answer to a problem on Fan's expansion method.     

A Linear Time Algorithm for L(2,1)-Labeling of Trees

An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)?f(y)|≥2 if x and y are adjacent and |f(x)?f(y)|≥1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)→{0,…,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ ^4.5 n) for more than a decade, and an O(min{n ^1.75,Δ ^1.5 n})-time algorithm has appeared recently, where Δ and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.     

On polynomial solutions of the linear stationary control system

It is known that the controllable system x′ = Bx + Du, where the x is the n-dimensional vector, can be transferred from an arbitrary initial state x(0) = x ⁰ to an arbitrary finite state x(T) = x ^T by the control function u(t) in the form of the polynomial in degrees t. In this work, the minimum degree of the polynomial is revised: it is equal to 2p + 1, where the number (p ? 1) is a minimum number of matrices in the controllability matrix (Kalman criterion), whose rank is equal to n. A simpler and a more natural algorithm is obtained, which first brings to the discovery of coefficients of a certain polynomial from the system of algebraic equations with the Wronskian and then, with the aid of differentiation, to the construction of functions of state and control.     

An upper bound for the distance between a zero and a critical point of a solution of a second order linear differential equation

This paper presents an upper bound for the distance between a zero and a critical point of a solution of the second order linear differential equation (p(x)y^′)^′+q(x)y(x)=0, with p(x),q(x)>0. It also compares it with previous results.     

Approximate Solutions of Polynomial Equations

In this paper, we introduce “approximate solutions" to solve the following problem: given a polynomial F(x, y) over Q, where x represents an n -tuple of variables, can we find all the polynomials G(x) such that F(x, G(x)) is identically equal to a constant c in Q ? We have the following: let F(x, y) be a polynomial over Q and the degree of y in F(x, y) be n. Either there is a unique polynomial g(x)  ∈ Q [ x ], with its constant term equal to 0, such that F(x, y)  = ∑_j = 0ⁿc_j(y − g(x))^jfor some rational numbers c_j, hence, F(x, g(x)  + a)  ∈ Q for all a ∈ Q, or there are at most t distinct polynomials g₁(x),⋯ , g_t(x), t ≤ n, such that F(x, g_i(x))  ∈ Q for 1  ≤ i ≤ t. Suppose that F(x, y) is a polynomial of two variables. The polynomial g(x) for the first case, or g₁(x),⋯ , g_t(x) for the second case, are approximate solutions of F(x, y), respectively. There is also a polynomial time algorithm to find all of these approximate solutions. We then use Kronecker’s substitution to solve the case of F(x, y).     

Trimmed Moebius Inversion and Graphs of Bounded Degree

We study ways to expedite Yates’s algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point, finishing the calculation at a subset before considering its supersets. For an n-element universe U and a family ? of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of U with k sets from ? in time within a polynomial factor (in n) of the number of supersets of the members of ?. Relying on an projection theorem of Chung et al. (J. Comb. Theory Ser. A 43:23–37, 1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs with maximum degree Δ. In particular, we show how to compute the domatic number in time within a polynomial factor of (2^Δ+1?2) ^n/(Δ+1) and the chromatic number in time within a polynomial factor of (2^Δ+1?Δ?1) ^n/(Δ+1). For any constant Δ, these bounds are O((2?ε) ⁿ ) for ε>0 independent of the number of vertices n.     

Distributed deterministic edge coloring using bounded neighborhood independence

We study the edge-coloring problem in the message-passing model of distributed computing. This is one of the most fundamental problems in this area. Currently, the best-known deterministic algorithms for (2Δ ?1)-edge-coloring requires O(Δ) +  log* n time (Panconesi and Rizzi in Distrib Comput 14(2):97–100, 2001), where Δ is the maximum degree of the input graph. Also, recent results of Barenboim and Elkin (2010) for vertex-coloring imply that one can get an O(Δ)-edge-coloring in ${O(\Delta^{\epsilon}\cdot \log n)}$ time, and an ${O(\Delta^{1 + \epsilon})}$ -edge-coloring in O(log Δ log n) time, for an arbitrarily small constant ${\epsilon > 0}$ . In this paper we devise a significantly faster deterministic edge-coloring algorithm. Specifically, our algorithm computes an O(Δ)-edge-coloring in ${O(\Delta^{\epsilon}) + \log* n}$ time, and an ${O(\Delta^{1 + \epsilon})}$ -edge-coloring in O(log Δ) +  log* n time. This result improves the state-of-the-art running time for deterministic edge-coloring with this number of colors in almost the entire range of maximum degree Δ. Moreover, it improves it exponentially in a wide range of Δ, specifically, for 2 ^Ω(log*n) ≤ Δ ≤ polylog(n). In addition, for small values of Δ (up to log^{1 - δ} n, for some fixed δ > 0) our deterministic algorithm outperforms all the existing randomized algorithms for this problem. Also, our algorithm is the first O(Δ)-edge-coloring algorithm that has running time o(Δ) + log* n, for the entire range of Δ. All previous (deterministic and randomized) O(Δ)-edge-coloring algorithms require ${\Omega(\min \{\Delta, \sqrt{\log n}\ \})}$ time. On our way to these results we study the vertex-coloring problem on graphs with bounded neighborhood independence. This is a large family of graphs, which strictly includes line graphs of r-hypergraphs (i.e., hypergraphs in which each hyperedge contains r or less vertices) for r =  O(1), and graphs of bounded growth. We devise a very fast deterministic algorithm for vertex-coloring graphs with bounded neighborhood independence. This algorithm directly gives rise to our edge-coloring algorithms, which apply to general graphs. Our main technical contribution is a subroutine that computes an O(Δ/p)-defective p-vertex coloring of graphs with bounded neighborhood independence in O(p ²) + log* n time, for a parameter p, 1 ≤ p ≤ Δ. In all previous efficient distributed routines for m-defective p-coloring the product m· p is super-linear in Δ. In our routine this product is linear in Δ, and this enables us to speed up the algorithm drastically.     

Fast Maximal Cliques Enumeration in Sparse Graphs

In this paper, we consider the problem of generating all maximal cliques in a sparse graph in polynomial delay. Given a graph G=(V,E) with n vertices and m edges, the latest and fastest polynomial delay algorithm for sparse graphs enumerates all maximal cliques in O(Δ ⁴) time delay, where Δ is the maximum degree of vertices. However, it requires an O(n?m) preprocessing time. We improve it in two aspects. First, our algorithm does not need preprocessing. Therefore, our algorithm is a truly polynomial delay algorithm. Second, our algorithm enumerates all maximal cliques in O(Δ?H ³) time delay, where H is the so called H-value of a graph or equivalently it is the smallest integer satisfying |{v∈V∣δ(v)≥H}|≤H given δ(v) as the degree of a vertex. In real-world network data, H usually is a small value and much smaller than Δ.