Hybridized Discontinuous Galerkin Method for Elliptic Interface Problems: Error Estimates Under Low Regularity Assumptions of Solutions

New hybridized discontinuous Galerkin (HDG) methods for the interface problem for elliptic equations are proposed. Unknown functions of our schemes are \(u_h\) in elements and \(\hat{u}_h\) on inter-element edges. That is, we formulate our schemes without introducing the flux variable. We assume that subdomains \(\Omega _1\) and \(\Omega _2\) are polyhedral domains and that the interface \(\Gamma =\partial \Omega _1\cap \partial \Omega _2\) is polyhedral surface or polygon. Moreover, \(\Gamma \) is assumed to be expressed as the union of edges of some elements. We deal with the case where the interface is transversely connected with the boundary of the whole domain \(\overline{\Omega }=\overline{\Omega _1\cap \Omega _2}\). Consequently, the solution u of the interface problem may not have a sufficient regularity, say \(u\in H^2(\Omega )\) or \(u|_{\Omega _1}\in H^2(\Omega _1)\), \(u|_{\Omega _2}\in H^2(\Omega _2)\). We succeed in deriving optimal order error estimates in an HDG norm and the \(L^2\) norm under low regularity assumptions of solutions, say \(u|_{\Omega _1}\in H^{1+s}(\Omega _1)\) and \(u|_{\Omega _2}\in H^{1+s}(\Omega _2)\) for some \(s\in (1/2,1]\), where \(H^{1+s}\) denotes the fractional order Sobolev space. Numerical examples to validate our results are also presented.     

Some methods for the numerical solution of variational inequalities with two obstacles

In this paper the problem \(\mathop {\min }\limits_{u \in K} \int\limits_\Omega {\left| {u_x } \right|^z dx} \) is studied. HereK≡{u∈W ₀ ¹ (Ω):ψ _i≤u≤ψ ₂}, whereψ ₁ andψ ₂ are given functions. The finite-dimensional discretization has been carried out both by the classical finite-difference method and by a «dnal» method whose corresponding finite-dimensional problem is solved by some new method in quadratic programming.     

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.     

Two generalized Wigner–Yanase skew information and their uncertainty relations

In this paper, we first define two generalized Wigner–Yanase skew information \(|K_{\rho ,\alpha }|(A)\) and \(|L_{\rho ,\alpha }|(A)\) for any non-Hermitian Hilbert–Schmidt operator A and a density operator \(\rho \) on a Hilbert space H and discuss some properties of them, respectively. We also introduce two related quantities \(|S_{\rho ,\alpha }|(A)\) and \(|T_{\rho ,\alpha }|(A)\). Then, we establish two uncertainty relations in terms of \(|W_{\rho ,\alpha }|(A)\) and \(|\widetilde{W}_{\rho ,\alpha }|(A)\), which read

$$\begin{aligned}&|W_{\rho ,\alpha }|(A)|W_{\rho ,\alpha }|(B)\ge \frac{1}{4}\left| \mathrm {tr}\left( \left[ \frac{\rho ^{\alpha }+\rho ^{1-\alpha }}{2} \right] ^{2}[A,B]^{0}\right) \right| ^{2},\\&\sqrt{|\widetilde{W}_{\rho ,\alpha }|(A)| \widetilde{W}_{\rho ,\alpha }|(B)}\ge \frac{1}{4} \left| \mathrm {tr}\left( \rho ^{2\alpha }[A,B]^{0}\right) \mathrm {tr} \left( \rho ^{2(1-\alpha )}[A,B]^{0}\right) \right| . \end{aligned}$$

     

Randomness Buys Depth for Approximate Counting

We show that the promise problem of distinguishing n-bit strings of relative Hamming weight \({1/2 + \Omega(1/{\rm lg}^{d-1} n)}\) from strings of weight \({1/2 - \Omega(1/{\rm \lg}^{d - 1} n)}\) can be solved by explicit, randomized (unbounded fan-in) poly(n)-size depth-d circuits with error \({\leq 1/3}\) , but cannot be solved by deterministic poly(n)-size depth-(d+1) circuits, for every \({d \geq 2}\) ; and the depth of both is tight. Our bounds match Ajtai’s simulation of randomized depth-d circuits by deterministic depth-(d + 2) circuits (Ann. Pure Appl. Logic; ’83) and provide an example where randomization buys resources. To rule out deterministic circuits, we combine Håstad’s switching lemma with an earlier depth-3 lower bound by the author (Computational Complexity 2009). To exhibit randomized circuits, we combine recent analyses by Amano (ICALP ’09) and Brody and Verbin (FOCS ’10) with derandomization. To make these circuits explicit, we construct a new, simple pseudorandom generator that fools tests \({A_1 \times A_2 \times \cdots \times A_{{\rm lg}{n}}}\) for \({A_i \subseteq [n], |A_{i}| = n/2}\) with error 1/n and seed length O(lg n), improving on the seed length \({\Omega({\rm lg}\, n\, {\rm lg}\, {\rm lg}\, n)}\) of previous constructions.     

A note on balanced immunity

For a finite alphabet ∑ we define a binary relation on \(2^{\Sigma *} \times 2^{2^{\Sigma ^* } } \) , called balanced immunity. A setB ? ∑* is said to be balancedC-immune (with respect to a classC ? 2^Σ* of sets) iff, for all infiniteL εC, $$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$ Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.     

Some properties of Rényi entropy over countably infinite alphabets

We study certain properties of Rényi entropy functionals $H_\alpha \left( \mathcal{P} \right)$ on the space of probability distributions over ?₊. Primarily, continuity and convergence issues are addressed. Some properties are shown to be parallel to those known in the finite alphabet case, while others illustrate a quite different behavior of the Rényi entropy in the infinite case. In particular, it is shown that for any distribution $\mathcal{P}$ and any r ∈ [0,∞] there exists a sequence of distributions $\mathcal{P}_n$ converging to $\mathcal{P}$ with respect to the total variation distance and such that $\mathop {\lim }\limits_{n \to \infty } \mathop {\lim }\limits_{\alpha \to 1 + } H_\alpha \left( {\mathcal{P}_n } \right) = \mathop {\lim }\limits_{\alpha \to 1 + } \mathop {\lim }\limits_{n \to \infty } H_\alpha \left( {\mathcal{P}_n } \right) + r$ .     

On the class of λ-statistically convergent difference sequences of fuzzy numbers

In this study, we introduce the sets $\left[ V,\lambda ,p\right] _{\Updelta }^{{\mathcal{F}}},\left[ C,1,p\right] _{\Updelta }^{{\mathcal{F}}}$ and examine their relations with the classes of $ S_{\lambda }\left( \Updelta ,{\mathcal{F}}\right)$ and $ S_{\mu }\left( \Updelta ,{\mathcal{F}}\right)$ of sequences for the sequences $\left( \lambda _{n}\right)$ and $\left( \mu _{n}\right) , 0<p<\infty $ and difference sequences of fuzzy numbers.     

Quantum search algorithm for set operation

The operations of data set, such as intersection, union and complement, are the fundamental calculation in mathematics. It’s very significant that designing fast algorithm for set operation. In this paper, the quantum algorithm for calculating intersection set ${\text{C}=\text{A}\cap \text{B}}$ is presented. Its runtime is ${O\left( {\sqrt{\left| A \right|\times \left| B \right|\times \left|C \right|}}\right)}$ for case ${\left| C \right|\neq \phi}$ and ${O\left( {\sqrt{\left| A \right|\times \left| B \right|}}\right)}$ for case ${\left| C \right|=\phi}$ (i.e. C is empty set), while classical computation needs O (|A| × |B|) steps of computation in general, where |.| denotes the size of set. The presented algorithm is the combination of Grover’s algorithm, classical memory and classical iterative computation, and the combination method decrease the complexity of designing quantum algorithm. The method can be used to design other set operations as well.     

Master Lovas–Andai and equivalent formulas verifying the $$\frac{8}{33}$$ two-qubit Hilbert–Schmidt separability probability and companion rational-valued conjectures

We begin by investigating relationships between two forms of Hilbert–Schmidt two-rebit and two-qubit “separability functions”—those recently advanced by Lovas and Andai (J Phys A Math Theor 50(29):295303, 2017), and those earlier presented by Slater (J Phys A 40(47):14279, 2007). In the Lovas–Andai framework, the independent variable \(\varepsilon \in [0,1]\) is the ratio \(\sigma (V)\) of the singular values of the \(2 \times 2\) matrix \(V=D_2^{1/2} D_1^{-1/2}\) formed from the two \(2 \times 2\) diagonal blocks (\(D_1, D_2\)) of a \(4 \times 4\) density matrix \(D= \left||\rho _{ij}\right||\). In the Slater setting, the independent variable \(\mu \) is the diagonal-entry ratio \(\sqrt{\frac{\rho _{11} \rho _ {44}}{\rho _ {22} \rho _ {33}}}\)—with, of central importance, \(\mu =\varepsilon \) or \(\mu =\frac{1}{\varepsilon }\) when both \(D_1\) and \(D_2\) are themselves diagonal. Lovas and Andai established that their two-rebit “separability function” \(\tilde{\chi }_1 (\varepsilon )\) (\(\approx \varepsilon \)) yields the previously conjectured Hilbert–Schmidt separability probability of \(\frac{29}{64}\). We are able, in the Slater framework (using cylindrical algebraic decompositions [CAD] to enforce positivity constraints), to reproduce this result. Further, we newly find its two-qubit, two-quater[nionic]-bit and “two-octo[nionic]-bit” counterparts, \(\tilde{\chi _2}(\varepsilon ) =\frac{1}{3} \varepsilon ^2 \left( 4-\varepsilon ^2\right) \), \(\tilde{\chi _4}(\varepsilon ) =\frac{1}{35} \varepsilon ^4 \left( 15 \varepsilon ^4-64 \varepsilon ^2+84\right) \) and \(\tilde{\chi _8} (\varepsilon )= \frac{1}{1287}\varepsilon ^8 \left( 1155 \varepsilon ^8-7680 \varepsilon ^6+20160 \varepsilon ^4-25088 \varepsilon ^2+12740\right) \). These immediately lead to predictions of Hilbert–Schmidt separability/PPT-probabilities of \(\frac{8}{33}\), \(\frac{26}{323}\) and \(\frac{44482}{4091349}\), in full agreement with those of the “concise formula” (Slater in J Phys A 46:445302, 2013), and, additionally, of a “specialized induced measure” formula. Then, we find a Lovas–Andai “master formula,” \(\tilde{\chi _d}(\varepsilon )= \frac{\varepsilon ^d \Gamma (d+1)^3 \, _3\tilde{F}_2\left( -\frac{d}{2},\frac{d}{2},d;\frac{d}{2}+1,\frac{3 d}{2}+1;\varepsilon ^2\right) }{\Gamma \left( \frac{d}{2}+1\right) ^2}\), encompassing both even and odd values of d. Remarkably, we are able to obtain the \(\tilde{\chi _d}(\varepsilon )\) formulas, \(d=1,2,4\), applicable to full (9-, 15-, 27-) dimensional sets of density matrices, by analyzing (6-, 9, 15-) dimensional sets, with not only diagonal \(D_1\) and \(D_2\), but also an additional pair of nullified entries. Nullification of a further pair still leads to X-matrices, for which a distinctly different, simple Dyson-index phenomenon is noted. C. Koutschan, then, using his HolonomicFunctions program, develops an order-4 recurrence satisfied by the predictions of the several formulas, establishing their equivalence. A two-qubit separability probability of \(1-\frac{256}{27 \pi ^2}\) is obtained based on the operator monotone function \(\sqrt{x}\), with the use of \(\tilde{\chi _2}(\varepsilon )\).     

Resource augmentation for uniprocessor and multiprocessor partitioned scheduling of sporadic real-time tasks

Although the earliest-deadline-first (EDF) policy is known to be optimal for preemptive real-time task scheduling in uniprocessor systems, the schedulability analysis problem has recently been shown to be $\mathit{co}\mathcal{NP}$ -hard. Therefore, approximation algorithms, and in particular, approximations based on resource augmentation have attracted a lot of attention for both uniprocessor and multiprocessor systems. Resource augmentation based approximations assume a certain speedup of the processor(s). Using the notion of approximate demand bound function (dbf), in this paper we show that for uniprocessor systems the resource augmentation factor is at most $\frac{2e-1}{e} \approx1.6322$ , where e is the Euler number. We approximate the dbf using a linear approximation when the analysis interval length of interest is larger than the relative deadline of the task. For identical multiprocessor systems with M processors and constrained-deadline task sets, we show that the deadline-monotonic partitioning (that has been proposed by Baruah and Fisher) with the approximate dbf leads to an approximation factor of $\frac{3e-1}{e}-\frac{1}{M} \approx 2.6322-\frac{1}{M}$ with respect to resource augmentation. We also show that the corresponding factor is $3-\frac{1}{M}$ for arbitrary-deadline task sets. The best known results so far were $3-\frac{1}{M}$ for constrained-deadline tasks and $4-\frac {2}{M}$ for arbitrary-deadline ones. Our tighter analysis exploits the structure of the approximate dbf directly and uses the processor utilization violations (which were ignored in all previous analysis) for analyzing resource augmentation factors. We also provide concrete input instances to show that the lower bound on the resource augmentation factor for uniprocessor systems—using the above approximate dbf—is 1.5, and the corresponding bound is 2.5 for identical multiprocessor systems with an arbitrary order of fitting and a large number of processors. Further, we also provide a polynomial-time approximation scheme (PTAS) to derive near-optimal solutions under the assumption that the ratio of the maximum relative deadline to the minimum relative deadline of tasks is a constant, which is a more relaxed assumption compared to the assumptions required for deriving such a PTAS in the past.     

Numerical evaluation of a solution of a special mixed-type differential-difference equation

The function * $$f(t) = \frac{{e^{ - \alpha \gamma } }}{\pi }\int\limits_0^\infty {\cos t \xi e^{\alpha Ci(\xi )} \frac{{d\xi }}{{\xi ^\alpha }},t \in R,\alpha > 0} $$ [Ci(x)=cosine integral, γ=Euler's constant] is studied and numerically evaluated;f is a solution to the following mixed type differential-difference equation arising in applied probability: ** $$tf'(t) = (\alpha - 1)f(t) - \frac{\alpha }{2}[f(t - 1) + f(t + 1)]$$ satisfying the conditions: i) $$f(t) \geqslant 0,t \in R$$ , ii) $$f(t) = f( - t),t \in R$$ , iii) $$\int\limits_{ - \infty }^{ + \infty } {f(\xi )d\xi = 1} $$ . Besides the direct numerical evaluation of (*) and the derivation of the asymptotic behaviour off(t) fort→0 andt→∞, two different iterative procedures for the solution of (**) under the conditions (i) to (iii) are considered and their results are compared with the corresponding values in (*). Finally a Monte Carlo method to evaluatef(t) is considered.     

Property Testing on k-Vertex-Connectivity of?Graphs

We present an algorithm for testing the k-vertex-connectivity of graphs with the given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. Fixed degree bound d, a graph G with n vertices and a maximum degree at most d is called ε-far from k-vertex-connectivity when at least $\frac{\epsilon dn}{2}$ edges must be added to or removed from G to obtain a k-vertex-connected graph with a maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is ε-far from k-vertex-connectivity with a probability of at least 2/3. The algorithm runs in $O(d(\frac{c}{\epsilon d})^{k}\log\frac {1}{\epsilon d})$ time (c>1 is a constant) for (k?1)-vertex-connected graphs, and in $O(d(\frac{ck}{\epsilon d})^{k}\log\frac{k}{\epsilon d})$ time (c>1 is a constant) for general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k≥4.     

On the inversion of a certain gram matrix

Two new proofs are given for the inversion of the matrix \(((r^2 - z_j \bar z_k )^{ - 1} )\) ,r>0 and |z _k Ç<r.     

Characterization of quantum circulant networks having perfect state transfer

In this paper we answer the question of when circulant quantum spin networks with nearest-neighbor couplings can give perfect state transfer. The network is described by a circulant graph G, which is characterized by its circulant adjacency matrix A. Formally, we say that there exists a perfect state transfer (PST) between vertices ${a,b\in V(G)}$ if |F(τ) _ab | = 1, for some positive real number τ, where F(t) = exp(i At). Saxena et al. (Int J Quantum Inf 5:417–430, 2007) proved that |F(τ) _aa | = 1 for some ${a\in V(G)}$ and ${\tau\in \mathbb {R}^+}$ if and only if all eigenvalues of G are integer (that is, the graph is integral). The integral circulant graph ICG _n (D) has the vertex set Z _n = {0, 1, 2, . . . , n ? 1} and vertices a and b are adjacent if ${\gcd(a-b,n)\in D}$ , where ${D \subseteq \{d : d \mid n, \ 1 \leq d < n\}}$ . These graphs are highly symmetric and have important applications in chemical graph theory. We show that ICG _n (D) has PST if and only if ${n\in 4\mathbb {N}}$ and ${D=\widetilde{D_3} \cup D_2\cup 2D_2\cup 4D_2\cup \{n/2^a\}}$ , where ${\widetilde{D_3}=\{d\in D\ |\ n/d\in 8\mathbb {N}\}, D_2= \{d\in D\ |\ n/d\in 8\mathbb {N}+4\}{\setminus}\{n/4\}}$ and ${a\in\{1,2\}}$ . We have thus answered the question of complete characterization of perfect state transfer in integral circulant graphs raised in Angeles-Canul et al. (Quantum Inf Comput 10(3&4):0325–0342, 2010). Furthermore, we also calculate perfect quantum communication distance (distance between vertices where PST occurs) and describe the spectra of integral circulant graphs having PST. We conclude by giving a closed form expression calculating the number of integral circulant graphs of a given order having PST.     

Multiple signal extraction by polynomial filtering

Let {U ₁ ,?,U_n} denote stochastic processes with imbedded signals {u ₁ ,?,u_n} respectively. A mapT is said to extract {u ₁,?,u_n} without distortion provided \(\xi _i = Tu_i , i = 1,...,n\) whereξ _i , i = 1,?,n are chosen apriori. The mapT is said to be optimal whenever it minimizes \(J(T) = E\sum\limits_i {||\Xi _\iota - TU_i ||^2 } \) whereΞ _i , i = i,?,n are suitable stochastic processes. The mapT is called an optimal distortion free signal extractor if it also is causal. This paper analyses polynomic optimal distortion free signal extractors.     

Quadrature rules for Prandtl's integral equation

In this paper we construct an interpolatory quadrature formula of the type $$\mathop {\rlap{--} \smallint }\limits_{ - 1}^1 \frac{{f'(x)}}{{y - x}}dx \approx \sum\limits_{i = 1}^n {w_{ni} (y)f(x_{ni} )} ,$$ wheref(x)=(1?x)^α(1+x)^β f _o(x), α, β>0, and {x _ni} are then zeros of then-th degree Chebyshev polynomial of the first kind,T _n (x). We also give a convergence result and examine the behavior of the quantity \( \sum\limits_{i = 1}^n {|w_{ni} (y)|} \) asn→∞.     

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.     

Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph?G, to find a series-parallel subgraph of?G with the maximum number of edges. The algorithm that, given a connected graph?G, outputs a spanning tree of?G, is a $\frac{1}{2}$ -approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has?n?1 edges and any series-parallel graph on?n vertices has at most?2n?3 edges. We present a $\frac{7}{12}$ -approximation for this problem and results showing the limits of our approach.