Solving Convection-Diffusion Problems on Curved Domains by Extensions from Subdomains

We present a technique for numerically solving convection-diffusion problems in domains $\varOmega $ with curved boundary. The technique consists in approximating the domain $\varOmega $ by polyhedral subdomains $\mathsf{{D}}_h$ where a finite element method is used to solve for the approximate solution. The approximation is then suitably extended to the remaining part of the domain $\varOmega $ . This approach allows for the use of only polyhedral elements; there is no need of fitting the boundary in order to obtain an accurate approximation of the solution. To achieve this, the boundary condition on the border of $\varOmega $ is transferred to the border of $\mathsf{D }_h$ by using simple line integrals. We apply this technique to the hybridizable discontinuous Galerkin method and provide extensive numerical experiments showing that, whenever the distance of $\mathsf{{D}}_h$ to $\partial \varOmega $ is of order of the meshsize $h$ , the convergence properties of the resulting method are the same as those for the case in which $\varOmega =\mathsf{{D}}_h$ . We also show numerical evidence indicating that the ratio of the $L^2(\varOmega )$ norm of the error in the scalar variable computed with $d>0$ to that of that computed with $d=0$ remains constant (and fairly close to one), whenever the distance $d$ is proportional to $\min \{h,Pe^{-1}\}/(k+1)^2$ , where $Pe$ is the so-called Péclet number.     

General DG-Methods for Highly Indefinite Helmholtz Problems

We develop a stability and convergence theory for a Discontinuous Galerkin formulation (DG) of a highly indefinite Helmholtz problem in $\mathbb R ^{d}$ , $d\in \{1,2,3\}$ . The theory covers conforming as well as non-conforming generalized finite element methods. In contrast to conventional Galerkin methods where a minimal resolution condition is necessary to guarantee the unique solvability, it is proved that the DG-method admits a unique solution under much weaker conditions. As an application we present the error analysis for the $hp$ -version of the finite element method explicitly in terms of the mesh width $h$ , polynomial degree $p$ and wavenumber $k$ . It is shown that the optimal convergence order estimate is obtained under the conditions that $kh/\sqrt{p}$ is sufficiently small and the polynomial degree $p$ is at least $O(\log k)$ . On regular meshes, the first condition is improved to the requirement that $kh/p$ be sufficiently small.     

Reduced ordered binary decision diagram with implied literals: a new knowledge compilation approach

Reduced ordered binary decision diagram (ROBDD) is one of the most influential knowledge compilation languages. We generalize it by associating some implied literals with each node to propose a new language called ROBDD with implied literals (ROBDD- $L$ ) and show that ROBDD- $L$ can meet most of the querying requirements involved in the knowledge compilation map. Then, we discuss a kind of subsets of ROBDD- $L$ called ROBDD- $L_i$ with precisely $i$ implied literals $(0\le i\le \infty )$ , where ROBDD- $L_0$ is isomorphic to ROBDD. ROBDD- $L_i$ has uniqueness over any given linear order of variables. We mainly focus on ROBDD- $L_\infty $ and demonstrate that: (a) it is a canonical representation on any given variable order; (b) it is the most succinct subset in ROBDD- $L$ and thus also meets most of the querying requirements; (c) given any logical operation ROBDD supports in polytime, ROBDD- $L_\infty $ can also support it in time polynomial in the sizes of the equivalent ROBDDs. Moreover, we propose an ROBDD- $L_i$ compilation algorithm for any $i$ and an ROBDD- $L_\infty $ compilation algorithm, and then we implement an ROBDD- $L$ package called BDDjLu. Our preliminary experimental results indicate that: (a) the compilation results of ROBDD- $L_\infty $ are significantly smaller than those of ROBDD; (b) the standard d-DNNF compiler c2d and our ROBDD- $L_\infty $ compiler do not dominate the other, yet ROBDD- $L_\infty $ has canonicity and supports more querying requirements and relatively efficient logical operations; and (c) the method that first compiles knowledge base into ROBDD- $L_\infty $ and then converts ROBDD- $L_\infty $ into ROBDD provides an efficient ROBDD compiler.     

The Compact Discontinuous Galerkin Method for Nearly Incompressible Linear Elasticity

A compact discontinuous Galerkin method (CDG) is devised for nearly incompressible linear elasticity, through replacing the global lifting operator for determining the numerical trace of stress tensor in a local discontinuous Galerkin method (cf. Chen et al., Math Probl Eng 20, 2010) by the local lifting operator and removing some jumping terms. It possesses the compact stencil, that means the degrees of freedom in one element are only connected to those in the immediate neighboring elements. Optimal error estimates in broken energy norm, $H^1$ -norm and $L^2$ -norm are derived for the method, which are uniform with respect to the Lamé constant $\lambda .$ Furthermore, we obtain a post-processed $H(\text{ div})$ -conforming displacement by projecting the displacement and corresponding trace of the CDG method into the Raviart–Thomas element space, and obtain optimal error estimates of this numerical solution in $H(\text{ div})$ -seminorm and $L^2$ -norm, which are uniform with respect to $\lambda .$ A series of numerical results are offered to illustrate the numerical performance of our method.     

Quantum secret sharing with continuous variable graph state

In this paper, we study several physically feasible quantum secret sharing (QSS) schemes using continuous variable graph state (CVGS). Their implementation protocols are given, and the estimation error formulae are derived. Then, we present a variety of results on the theory of QSS with CVGS. Any $(k,n)$ threshold protocol of the three specific schemes satisfying $\frac{n}{2}<k\le n$ , where $n$ denotes the total number of players and $k$ denotes the minimum number of players who can collaboratively access the secret, can be implemented by certain weighted CVGS. The quantum secret is absolutely confidential to any player group with number less than threshold. Besides, the effect of finite squeezing to these results is properly considered. In the end, the duality between two specific schemes is investigated.     

A C^0-Weak Galerkin Finite Element Method for the Biharmonic Equation

A $C^0$ -weak Galerkin (WG) method is introduced and analyzed in this article for solving the biharmonic equation in 2D and 3D. A discrete weak Laplacian is defined for $C^0$ functions, which is then used to design the weak Galerkin finite element scheme. This WG finite element formulation is symmetric, positive definite and parameter free. Optimal order error estimates are established for the weak Galerkin finite element solution in both a discrete $H^2$ norm and the standard $H^1$ and $L^2$ norms with appropriate regularity assumptions. Numerical results are presented to confirm the theory. As a technical tool, a refined Scott-Zhang interpolation operator is constructed to assist the corresponding error estimates. This refined interpolation preserves the volume mass of order $(k+1-d)$ and the surface mass of order $(k+2-d)$ for the $P_{k+2}$ finite element functions in $d$ -dimensional space.     

The Local Discontinuous Galerkin Method for the Fourth-Order Euler–Bernoulli Partial Differential Equation in One Space Dimension. Part I: Superconvergence Error Analysis

In this paper we develop and analyze a new superconvergent local discontinuous Galerkin (LDG) method for approximating solutions to the fourth-order Euler–Bernoulli beam equation in one space dimension. We prove the $L^2$ stability of the scheme and several optimal $L^2$ error estimates for the solution and for the three auxiliary variables that approximate derivatives of different orders. Our numerical experiments demonstrate optimal rates of convergence. We also prove superconvergence results towards particular projections of the exact solutions. More precisely, we prove that the LDG solution and its spatial derivatives (up to third order) are $\mathcal O (h^{k+3/2})$ super close to particular projections of the exact solutions for $k$ th-degree polynomial spaces while computational results show higher $\mathcal O (h^{k+2})$ convergence rate. Our proofs are valid for arbitrary regular meshes and for $P^k$ polynomials with $k\ge 1$ , and for periodic, Dirichlet, and mixed boundary conditions. These superconvergence results will be used to construct asymptotically exact a posteriori error estimates by solving a local steady problem on each element. This will be reported in Part II of this work, where we will prove that the a posteriori LDG error estimates for the solution and its derivatives converge to the true errors in the $L^2$ -norm under mesh refinement.     

Null controllability of Kolmogorov-type equations

We study the null controllability of Kolmogorov-type equations $\partial _t f + v^\gamma \partial _x f - \partial _v^2 f = u(t,x,v) 1_{\omega }(x,v)$ in a rectangle $\Omega $ , under an additive control supported in an open subset $\omega $ of $\Omega $ . For $\gamma =1$ , with periodic-type boundary conditions, we prove that null controllability holds in any positive time, with any control support $\omega $ . This improves the previous result by Beauchard and Zuazua (Ann Ins H Poincaré Anal Non Linéaire 26:1793–1815, 2009), in which the control support was a horizontal strip. With Dirichlet boundary conditions and a horizontal strip as control support, we prove that null controllability holds in any positive time if $\gamma =1$ or if $\gamma =2$ and $\omega $ contains the segment $\{v=0\}$ , and only in large time if $\gamma =2$ and $\omega $ does not contain the segment $\{v=0\}$ . Our approach, inspired from Benabdallah et al. (C R Math Acad Sci Paris 344(6):357–362, 2007), Lebeau and Robbiano (Commun Partial Differ Equ 20:335–356, 1995), is based on two key ingredients: the observability of the Fourier components of the solution of the adjoint system, uniformly with respect to the frequency, and the explicit exponential decay rate of these Fourier components.     

An Efficient High-Order Time Integration Method for Spectral-Element Discontinuous Galerkin Simulations in Electromagnetics

We investigate efficient algorithms and a practical implementation of an explicit-type high-order timestepping method based on Krylov subspace approximations, for possible application to large-scale engineering problems in electromagnetics. We consider a semi-discrete form of the Maxwell’s equations resulting from a high-order spectral-element discontinuous Galerkin discretization in space whose solution can be expressed analytically by a large matrix exponential of dimension $\kappa \times \kappa $ . We project the matrix exponential into a small Krylov subspace by the Arnoldi process based on the modified Gram–Schmidt algorithm and perform a matrix exponential operation with a much smaller matrix of dimension $m\times m$ ( $m\ll \kappa $ ). For computing the matrix exponential, we obtain eigenvalues of the $m\times m$ matrix using available library packages and compute an ordinary exponential function for the eigenvalues. The scheme involves mainly matrix-vector multiplications, and its convergence rate is generally $O(\Delta t^{m-1})$ in time so that it allows taking a larger timestep size as $m$ increases. We demonstrate CPU time reduction compared with results from the five-stage fourth-order Runge–Kutta method for a certain accuracy. We also demonstrate error behaviors for long-time simulations. Case studies are also presented, showing loss of orthogonality that can be recovered by adding a low-cost reorthogonalization technique.     

A Linear Iteration Algorithm for a Second-Order Energy Stable Scheme for a Thin Film Model Without Slope Selection

We present a linear iteration algorithm to implement a second-order energy stable numerical scheme for a model of epitaxial thin film growth without slope selection. The PDE, which is a nonlinear, fourth-order parabolic equation, is the $L^2$ gradient flow of the energy $ \int _\Omega \left( - \frac{1}{2} \ln \left( 1 + | \nabla \phi |^2 \right) + \frac{\epsilon ^2}{2}|\Delta \phi (\mathbf{x})|^2 \right) \mathrm{d}\mathbf{x}$ . The energy stability is preserved by a careful choice of the second-order temporal approximation for the nonlinear term, as reported in recent work (Shen et al. in SIAM J Numer Anal 50:105–125, 2012). The resulting scheme is highly nonlinear, and its implementation is non-trivial. In this paper, we propose a linear iteration algorithm to solve the resulting nonlinear system. To accomplish this we introduce an $O(s^2)$ (with $s$ the time step size) artificial diffusion term, a Douglas-Dupont-type regularization, that leads to a contraction mapping property. As a result, the highly nonlinear system can be decomposed as an iteration of purely linear solvers, which can be very efficiently implemented with the help of FFT in a collocation Fourier spectral setting. We present a careful analysis showing convergence for the numerical scheme in a discrete $L^\infty (0, T; H^1) \cap L^2 (0,T; H^3)$ norm. Some numerical simulation results are presented to demonstrate the efficiency of the linear iteration solver and the convergence of the scheme as a whole.     

On reducing factorization to the discrete logarithm problem modulo a composite

The discrete logarithm problem modulo a composite??abbreviate it as DLPC??is the following: given a (possibly) composite integer n??? 1 and elements ${a, b \in \mathbb{Z}_n^*}$ , determine an ${x \in \mathbb{N}}$ satisfying a ^x ?=?b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem ${{\rm DLPC}_\varepsilon}$ obtained by adding in the DLPC the constraint ${x\le (1-\varepsilon)n}$ , where ${\varepsilon}$ is an arbitrary fixed number, ${0 < \varepsilon\le\frac{1}{2}}$ . We prove that factoring n reduces in deterministic subexponential time to the ${{\rm DLPC}_\varepsilon}$ with ${O_\varepsilon((\ln n)^2)}$ queries for moduli less or equal to n.     

Arithmetizing Classes Around \textsf{NC} 1 and \textsf{L}

The parallel complexity class $\textsf{NC}$ ¹ has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ ¹ and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ ¹. We also consider polynomial-degree restrictions of $\textsf{SC}$ ⁱ , denoted $\textsf{sSC}$ ⁱ , and show that the Boolean class $\textsf{sSC}$ ¹ is sandwiched between $\textsf{NC}$ ¹ and $\textsf{L}$ , whereas $\textsf{sSC}$ ⁰ equals $\textsf{NC}$ ¹. On the other hand, the arithmetic class $\textsf{\#sSC}$ ⁰ contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ ¹ contains $\textsf{\#NC}$ ¹ and is in $\textsf{SC}$ ². We also investigate some closure properties of the newly defined arithmetic classes.     

Greedy routing in small-world networks with power-law degrees

In this paper we study decentralized routing in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we consider a variant of J. Kleinberg’s grid-based small-world model in which (1) the number of long-range edges of each node is not fixed, but is drawn from a power-law probability distribution with exponent parameter \(\alpha \ge 0\) and constant mean, and (2) the long-range edges are considered to be bidirectional for the purposes of routing. This model is motivated by empirical observations indicating that several real networks have degrees that follow a power-law distribution. The measured power-law exponent \(\alpha \) for these networks is often in the range between 2 and 3. For the small-world model we consider, we show that when \(2 < \alpha < 3\) the standard greedy routing algorithm, in which a node forwards the message to its neighbor that is closest to the target in the grid, finishes in an expected number of \(O(\log ^{\alpha -1} n\cdot \log \log n)\) steps, for any source–target pair. This is asymptotically smaller than the \(O(\log ^2 n)\) steps needed in Kleinberg’s original model with the same average degree, and approaches \(O(\log n)\) as \(\alpha \) approaches 2. Further, we show that when \(0\le \alpha < 2\) or \(\alpha \ge 3\) the expected number of steps is \(O(\log ^2 n)\) , while for \(\alpha = 2\) it is \(O(\log ^{4/3} n)\) . We complement these results with lower bounds that match the upper bounds within at most a \(\log \log n\) factor.     

Distinguishing and relating higher-order and first-order processes by expressiveness

This is a paper on distinguishing and relating two important kinds of calculi through expressiveness, settling some critical but long unanswered questions. The delimitation of higher-order and first-order process calculi is a basic and pivotal topic in the study of process theory. Particularly, expressiveness studies mutual encodability, which helps decide whether process-passing or name-passing is more fundamental, and the way they ought to be used in both theory and practice. In this paper, we contribute to such demarcation with three major results. Firstly $\pi $ (first-order pi-calculus) can faithfully express $\varPi $ (basic higher-order pi-calculus). The calculus $\varPi $ has the elementary operators (input, output, composition and restriction). This actually is a corollary of a more general result, that $\pi $ can encode $\varPi ^r$ ( $\varPi $ enriched with the relabelling operator). Secondly $\varPi $ cannot interpret $\pi $ reasonably. This is of more significance since it separates $\varPi $ and $\pi $ by drawing a well-defined boundary. Thirdly an encoding from $\pi $ to $\varPi ^r$ is revisited and discussed, which not only implies how to make $\varPi $ more useful but also stresses the importance of name-passing in $\pi $ .     

Parameterized complexity of three edge contraction problems with degree constraints

For any graph class \(\mathcal{H}\) , the \(\mathcal{H}\) -Contraction problem takes as input a graph \(G\) and an integer \(k\) , and asks whether there exists a graph \(H\in \mathcal{H}\) such that \(G\) can be modified into \(H\) using at most \(k\) edge contractions. We study the parameterized complexity of \(\mathcal{H}\) -Contraction for three different classes \(\mathcal{H}\) : the class \(\mathcal{H}_{\le d}\) of graphs with maximum degree at most  \(d\) , the class \(\mathcal{H}_{=d}\) of \(d\) -regular graphs, and the class of \(d\) -degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters \(k\) , \(d\) , and \(d+k\) . Moreover, we show that \(\mathcal{H}\) -Contraction admits an \(O(k)\) vertex kernel on connected graphs when \(\mathcal{H}\in \{\mathcal{H}_{\le 2},\mathcal{H}_{=2}\}\) , while the problem is \(\mathsf{W}[2]\) -hard when \(\mathcal{H}\) is the class of \(2\) -degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that \(\mathcal{H}\) -Contraction admits a linear vertex kernel when \(\mathcal{H}\) is the class of cycles.     

Two-Grid Methods for Hermitian positive definite linear systems connected with an order relation

Given a multigrid procedure for linear systems with coefficient matrices $A_n,$ we discuss the optimality of a related multigrid procedure with the same smoother and the same projector, when applied to properly related algebraic problems with coefficient matrices $B_n$ : we assume that both $A_n$ and $B_n$ are Hermitian positive definite with $A_n\le \vartheta B_n,$ for some positive $\vartheta $ independent of $n.$ In this context we prove the Two-Grid Method optimality. We apply this elementary strategy for designing a multigrid solution for modifications of multilevel structured linear systems, in which the Hermitian positive definite coefficient matrix is banded in a multilevel sense. As structured matrices, Toeplitz, circulants, Hartley, sine ( $\tau $ class) and cosine algebras are considered. In such a way, several linear systems arising from the approximation of integro–differential equations with various boundary conditions can be efficiently solved in linear time (with respect to the size of the algebraic problem). Some numerical experiments are presented and discussed, both with respect to Two-Grid and multigrid procedures.     

A P_N P_M{-} CPR Framework for Hyperbolic Conservation Laws

The correction procedure via reconstruction (CPR) method is a discontinuous nodal formulation unifying several well-known methods in a simple finite difference like manner. The \(P_NP_M{-} CPR \) formulation is an extension of \(P_NP_M\) or the reconstructed discontinuous Galerkin (RDG) method to the CPR framework. It is a hybrid finite volume and discontinuous Galerkin (DG) method, in which neighboring cells are used to build a higher order polynomial than the solution representation in the cell under consideration. In this paper, we present several \(P_NP_M\) schemes under the CPR framework. Many interesting schemes with various orders of accuracy and efficiency are developed. The dispersion and dissipation properties of those methods are investigated through a Fourier analysis, which shows that the \(P_NP_M{-} CPR \) method is dependent on the position of the solution points. Optimal solution points for 1D \(P_NP_M{-} CPR \) schemes which can produce expected order of accuracy are identified. In addition, the \(P_NP_M{-} CPR \) method is extended to solve 2D inviscid flow governed by the Euler equations and several numerical tests are performed to assess its performance.     

Optimal quadrature formulas in the sense of Sard in W_2^{(m,m-1)} space

This paper studies the problem of construction of optimal quadrature formulas in the sense of Sard in the $W_2^{(m,m-1)}(0,1)$ space. Using the Sobolev’s method we obtain new optimal quadrature formulas of such type for $N+1\ge m$ , where $N+1$ is the number of the nodes. Moreover, explicit formulas of the optimal coefficients are obtained. We investigate the order of convergence of the optimal formula for $m=1$ and prove an asymptotic optimality of such a formula in the Sobolev space $L_2^{(1)}(0,1)$ . It turns out that the error of the optimal quadrature formula in $W_2^{(1,0)}(0,1)$ is less than the error of the optimal quadrature formula given in the $L_2^{(1)}(0,1)$ space. The obtained optimal quadrature formula in the $W_2^{(m,m-1)}(0,1)$ space is exact for $\exp (-x)$ and $P_{m-2}(x)$ , where $P_{m-2}(x)$ is a polynomial of degree $m-2$ . Furthermore, some numerical results, which confirm the obtained theoretical results of this work, are given.     

A new set of generators and a physical interpretation for the SU (3) finite subgroup D(9,1,1;2,1,1)

After 100 years of effort, the classification of all the finite subgroups of $SU(3)$ is yet incomplete. The most recently updated list can be found in Ludl (J Phys A Math Theory 44:255204, 2011), where the structure of the series $(C)$ and $(D)$ of $SU(3)$ -subgroups is studied. We provide a minimal set of generators for one of these groups which has order $162$ . These generators appear up to phase as the image of an irreducible unitary braid group representation issued from the Jones–Kauffman version of $SU(2)$ Chern–Simons theory at level $4$ . In light of these new generators, we study the structure of the group in detail and recover the fact that it is isomorphic to the semidirect product $\mathbb Z _9\times \mathbb Z _3\rtimes S_3$ with respect to conjugation.