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.     

Locality and checkability in wait-free computing

This paper studies notions of locality that are inherent to the specification of distributed tasks by identifying fundamental relationships between the various scales of computation, from the individual process to the whole system. A locality property called projection-closed is identified. This property completely characterizes tasks that are wait-free checkable, where a task $T =(\mathcal{I },\mathcal{O },\varDelta )$ T = ( I , O , Δ ) is said to be checkable if there exists a distributed algorithm that, given $s\in \mathcal{I }$ s ∈ I and $t\in \mathcal{O }$ t ∈ O , determines whether $t\in \varDelta {(s)}$ t ∈ Δ ( s ) , i.e., whether $t$ t is a valid output for $s$ s according to the specification of $T$ T . Projection-closed tasks are proved to form a rich class of tasks. In particular, determining whether a projection-closed task is wait-free solvable is shown to be undecidable. A stronger notion of locality is identified by considering tasks whose outputs “look identical” to the inputs at every process: a task $T= (\mathcal{I },\mathcal{O },\varDelta )$ T = ( I , O , Δ ) is said to be locality-preserving if $\mathcal{O }$ O is a covering complex of $\mathcal{I }$ I . We show that this topological property yields obstacles for wait-free solvability different in nature from the classical impossibility results. On the other hand, locality-preserving tasks are projection-closed, and thus they are wait-free checkable. A classification of locality-preserving tasks in term of their relative computational power is provided. This is achieved by defining a correspondence between subgroups of the edgepath group of an input complex and locality-preserving tasks. This correspondence enables to demonstrate the existence of hierarchies of locality-preserving tasks, each one containing, at the top, the universal task (induced by the universal covering complex), and, at the bottom, the trivial identity task.     

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.     

Numerical investigation of homogenized Stokes–Nernst–Planck–Poisson systems

We consider charged transport within a porous medium, which at the pore scale can be described by the non-stationary Stokes–Nernst–Planck–Poisson (SNPP) system. We state three different homogenization results using the method of two-scale convergence. In addition to the averaged macroscopic equations, auxiliary cell problems are solved in order to provide closed-form expressions for effective coefficients. Our aim is to study numerically the convergence of the models for vanishing microstructure, i. e., the behavior for $\varepsilon \rightarrow 0$ ε → 0 , where $\varepsilon $ ε is the characteristic ratio between pore diameter and size of the porous medium. To this end, we propose a numerical scheme capable of solving the fully coupled microscopic SNPP system and also the corresponding averaged systems. The discretization is performed fully implicitly in time using mixed finite elements in two space dimensions. The averaged models are evaluated using simulation results and their approximation errors in terms of $\varepsilon $ ε are estimated numerically.     

Quantum discord in spin systems with dipole–dipole interaction

The behavior of total quantum correlations (discord) in dimers consisting of dipolar-coupled spins 1/2 are studied. We found that the discord $Q=0$ at absolute zero temperature. As the temperature $T$ increases, the quantum correlations in the system increase at first from zero to its maximum and then decrease to zero according to the asymptotic law $T^{-2}$ . It is also shown that in absence of external magnetic field $B$ , the classical correlations $C$ at $T\rightarrow 0$ are, vice versa, maximal. Our calculations predict that in crystalline gypsum $\hbox {CaSO}_{4}\cdot \hbox {2H}_{2}{\hbox {O}}$ the value of natural $(B=0)$ quantum discord between nuclear spins of hydrogen atoms is maximal at the temperature of 0.644  $\upmu $ K, and for 1,2-dichloroethane $\hbox {H}_{2}$ ClC– $\hbox {CH}_{2}{\hbox {Cl}}$ the discord achieves the largest value at $T=0.517~\upmu $ K. In both cases, the discord equals $Q\approx 0.083$  bit/dimer what is $8.3\,\%$ of its upper limit in two-qubit systems. We estimate also that for gypsum at room temperature $Q\sim 10^{-18}$  bit/dimer, and for 1,2-dichloroethane at $T=90$  K the discord is $Q\sim 10^{-17}$  bit per a dimer.     

Derandomized Parallel Repetition Theorems for Free Games

Raz’s parallel repetition theorem (SIAM J Comput 27(3):763–803, 1998) together with improvements of Holenstein (STOC, pp 411–419, 2007) shows that for any two-prover one-round game with value at most ${1- \epsilon}$ 1 - ? (for ${\epsilon \leq 1/2}$ ? ≤ 1 / 2 ), the value of the game repeated n times in parallel on independent inputs is at most ${(1- \epsilon)^{\Omega(\frac{\epsilon^2 n}{\ell})}}$ ( 1 - ? ) Ω ( ? 2 n ? ) , where ? is the answer length of the game. For free games (which are games in which the inputs to the two players are uniform and independent), the constant 2 can be replaced with 1 by a result of Barak et al. (APPROX-RANDOM, pp 352–365, 2009). Consequently, ${n=O(\frac{t \ell}{\epsilon})}$ n = O ( t ? ? ) repetitions suffice to reduce the value of a free game from ${1- \epsilon}$ 1 - ? to ${(1- \epsilon)^t}$ ( 1 - ? ) t , and denoting the input length of the game by m, it follows that ${nm=O(\frac{t \ell m}{\epsilon})}$ n m = O ( t ? m ? ) random bits can be used to prepare n independent inputs for the parallel repetition game. In this paper, we prove a derandomized version of the parallel repetition theorem for free games and show that O(t(m + ?)) random bits can be used to generate correlated inputs, such that the value of the parallel repetition game on these inputs has the same behavior. That is, it is possible to reduce the value from ${1- \epsilon}$ 1 - ? to ${(1- \epsilon)^t}$ ( 1 - ? ) t while only multiplying the randomness complexity by O(t) when m = O(?). Our technique uses strong extractors to “derandomize” a lemma of Raz and can be also used to derandomize a parallel repetition theorem of Parnafes et al. (STOC, pp 363–372, 1997) for communication games in the special case that the game is free.     

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.     

Interpolation splines minimizing a semi-norm

Using S.L. Sobolev’s method, we construct the interpolation splines minimizing the semi-norm in $K_2(P_2)$ , where $K_2(P_2)$ is the space of functions $\phi $ such that $\phi ^{\prime } $ is absolutely continuous, $\phi ^{\prime \prime } $ belongs to $L_2(0,1)$ and $\int _0^1(\varphi ^{\prime \prime }(x)+\varphi (x))^2dx<\infty $ . Explicit formulas for coefficients of the interpolation splines are obtained. The resulting interpolation spline is exact for the trigonometric functions $\sin x$ and $\cos x$ . Finally, in a few numerical examples the qualities of the defined splines and $D^2$ -splines are compared. Furthermore, the relationship of the defined splines with an optimal quadrature formula is shown.     

Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times

We study the problem of maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times. Unlike the vast majority of the literature, we do not restrict ourselves to a specific model of processing time function. Rather, we assume that the processing time function can be of any functional structure that is according to one of the following two cases. The first is the case where the job processing times are under a learning effect, i.e., each job processing time is a non-increasing function of its position in the sequence. In the second case, an aging effect is assumed, i.e., each job processing time is a non-decreasing function of its position in the sequence. We prove that the problem is strongly $\mathcal{N }\mathcal{P }$ N P -hard under a learning effect, even if all the weights are identical. When there is an aging effect, we introduce a dynamic programming (DP) procedure that solves the problem with arbitrary weights in $O(n^{3})$ O ( n 3 ) time (where $n$ n is the number of jobs). For identical weights, a faster optimization algorithm that runs in $O(n\log n)$ O ( n log n ) time is presented. We also extend the analysis to the case of scheduling on a set of $m$ m parallel unrelated machines and provide a DP procedure that solves the problem in polynomial time, given that $m$ m is fixed and that the jobs are under an aging effect.     

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 $ .     

The Relationships Between Chebyshev,Legendre and Jacobi Polynomials: The Generic Superiority of Chebyshev Polynomials and Three Important Exceptions

We analyze the asymptotic rates of convergence of Chebyshev, Legendre and Jacobi polynomials. One complication is that there are many reasonable measures of optimality as enumerated here. Another is that there are at least three exceptions to the general principle that Chebyshev polynomials give the fastest rate of convergence from the larger family of Jacobi polynomials. When $f(x)$ is singular at one or both endpoints, all Gegenbauer polynomials (including Legendre and Chebyshev) converge equally fast at the endpoints, but Gegenbauer polynomials converge more rapidly on the interior with increasing order $m$ . For functions on the surface of the sphere, associated Legendre functions, which are proportional to Gegenbauer polynomials, are best for the latitudinal dependence. Similarly, for functions on the unit disk, Zernike polynomials, which are Jacobi polynomials in radius, are superior in rate-of-convergence to a Chebyshev–Fourier series. It is true, as was conjectured by Lanczos 60 years ago, that excluding these exceptions, the Chebyshev coefficients $a_{n}$ usually decrease faster than the Legendre coefficients $b_{n}$ by a factor of $\sqrt{n}$ . We calculate the proportionality constant for a few examples and restrictive classes of functions. The more precise claim that $b_{n} \sim \sqrt{\pi /2} \sqrt{n} a_{n}$ , made by Lanczos and later Fox and Parker, is true only for rather special functions. However, individual terms in the large $n$ asymptotics of Chebyshev and Legendre coefficients usually do display this proportionality.     

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.     

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.     

Time versus space trade-offs for rendezvous in trees

Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with $k$ memory bits, we show that optimal rendezvous time is $\Theta (n+n^2/k)$ in $n$ -node trees. More precisely, if $k \ge c\log n$ , for some constant $c$ , we design agents accomplishing rendezvous in arbitrary trees of size $n$ (unknown to the agents) in time $O(n+n^2/k)$ , starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time $o(n+n^2/k)$ , even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a $n$ -node line.     

\lambda -Statistical convergence of fuzzy numbers and fuzzy functions of order \theta

In this paper, we introduce the concept of $\lambda $ -statistical convergence of order $\theta $ and strong $\lambda $ -summability of order $\theta $ for the sequence of fuzzy numbers. Further the same concept is extended to the sequence of fuzzy functions and introduce the spaces like $S_\lambda ^\theta (\hat{f})$ and $\omega _{\lambda p} ^\theta (\hat{f})$ . Some inclusion relations in those spaces and also the underlying relation between these two spaces are also obtained.     

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.     

The Rank-Width of Edge-Coloured Graphs

A C-coloured graph is a graph, that is possibly directed, where the edges are coloured with colours from the set C. Clique-width is a complexity measure for C-coloured graphs, for finite sets C. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss some possible extensions of the notion of rank-width to C-coloured graphs. There is not a unique natural notion of rank-width for C-coloured graphs. We define two notions of rank-width for them, both based on a coding of C-coloured graphs by ${\mathbb{F}}^{*}$ -graphs— $\mathbb {F}$ -coloured graphs where each edge has exactly one colour from $\mathbb{F}\setminus \{0\},\ \mathbb{F}$ a field—and named respectively $\mathbb{F}$ -rank-width and $\mathbb {F}$ -bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for $\mathbb{F}^{*}$ -graphs and prove that $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width are characterised by a list of $\mathbb{F}^{*}$ -graphs to exclude as vertex-minors (this list is finite if $\mathbb{F}$ is finite). An algorithm that decides in time O(n ³) whether an $\mathbb{F}^{*}$ -graph with n vertices has $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) at most k, for fixed k and fixed finite field $\mathbb{F}$ , is also given. Graph operations to check MSOL-definable properties on $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) are presented. A specialisation of all these notions to graphs without edge colours is presented, which shows that our results generalise the ones in undirected graphs.     

Maps on a quantum logic

In this paper we will study functions G of two variables on a quantum logic L, such that for each compatible elements $a,b\in L,$ $G(a,b)=m(a\wedge b)$ or $ G(a,b)=m(a\vee b)$ or $G(a,b)=m(a\triangle b),$ where m is a state on L.     

Uncertainty and certainty relations for complementary qubit observables in terms of Tsallis’ entropies

Uncertainty relations for more than two observables have found use in quantum information, though commonly known relations pertain to a pair of observables. We present novel uncertainty and certainty relations of state-independent form for the three Pauli observables with use of the Tsallis $\alpha $ -entropies. For all real $\alpha \in (0;1]$ and integer $\alpha \ge 2$ , lower bounds on the sum of three $\alpha $ -entropies are obtained. These bounds are tight in the sense that they are always reached with certain pure states. The necessary and sufficient condition for equality is that the qubit state is an eigenstate of one of the Pauli observables. Using concavity with respect to the parameter $\alpha $ , we derive approximate lower bounds for non-integer $\alpha \in (1;+\infty )$ . In the case of pure states, the developed method also allows to obtain upper bounds on the entropic sum for real $\alpha \in (0;1]$ and integer $\alpha \ge 2$ . For applied purposes, entropic bounds are often used with averaging over the individual entropies. Combining the obtained bounds leads to a band, in which the rescaled average $\alpha $ -entropy ranges in the pure-state case. A width of this band is essentially dependent on $\alpha $ . It can be interpreted as an evidence for sensitivity in quantifying the complementarity.     

Geometric discord and measurement-induced nonlocality for well known bound entangled states

We employ geometric discord and measurement induced nonlocality to quantify quantumness of some well-known bipartite bound entangled states, namely the two families of Horodecki’s ( $2\otimes 4, 3\otimes 3$ and $4\otimes 4$ dimensional) bound entangled states and that of Bennett et al.’s in $3\otimes 3$ dimension. In most of the cases our results are analytic and both the measures attain relatively small value. The amount of quantumness in the $4\otimes 4$ bound entangled state of Benatti et al. and the $2\otimes 8$ state having the same matrix representation (in computational basis) is same. Coincidently, the $2m\otimes 2m$ Werner and isotropic states also exhibit the same property, when seen as $2\otimes 2m^2$ dimensional states.