Two Mixed Finite Element Methods for Time-Fractional Diffusion Equations

Based on spatial conforming and nonconforming mixed finite element methods combined with classical L1 time stepping method, two fully-discrete approximate schemes with unconditional stability are first established for the time-fractional diffusion equation with Caputo derivative of order \(0<\alpha <1\). As to the conforming scheme, the spatial global superconvergence and temporal convergence order of \(O(h^2+\tau ^{2-\alpha })\) for both the original variable u in \(H^1\)-norm and the flux \(\vec {p}=\nabla u\) in \(L^2\)-norm are derived by virtue of properties of bilinear element and interpolation postprocessing operator, where h and \(\tau \) are the step sizes in space and time, respectively. At the same time, the optimal convergence rates in time and space for the nonconforming scheme are also investigated by some special characters of \(\textit{EQ}_1^{\textit{rot}}\) nonconforming element, which manifests that convergence orders of \(O(h+\tau ^{2-\alpha })\) and \(O(h^2+\tau ^{2-\alpha })\) for the original variable u in broken \(H^1\)-norm and \(L^2\)-norm, respectively, and approximation for the flux \(\vec {p}\) converging with order \(O(h+\tau ^{2-\alpha })\) in \(L^2\)-norm. Numerical examples are provided to demonstrate the theoretical analysis.     

Faster search by lackadaisical quantum walk

In the typical model, a discrete-time coined quantum walk searching the 2D grid for a marked vertex achieves a success probability of \(O(1/\log N)\) in \(O(\sqrt{N \log N})\) steps, which with amplitude amplification yields an overall runtime of \(O(\sqrt{N} \log N)\). We show that making the quantum walk lackadaisical or lazy by adding a self-loop of weight 4 / N to each vertex speeds up the search, causing the success probability to reach a constant near 1 in \(O(\sqrt{N \log N})\) steps, thus yielding an \(O(\sqrt{\log N})\) improvement over the typical, loopless algorithm. This improved runtime matches the best known quantum algorithms for this search problem. Our results are based on numerical simulations since the algorithm is not an instance of the abstract search algorithm.     

The hierarchical Petersen network: a new interconnection network with fixed degree

Network cost and fixed-degree characteristic for the graph are important factors to evaluate interconnection networks. In this paper, we propose hierarchical Petersen network (HPN) that is constructed in recursive and hierarchical structure based on a Petersen graph as a basic module. The degree of HPN(n) is 5, and HPN(n) has \(10^n\) nodes and \(2.5 \times 10^n\) edges. And we analyze its basic topological properties, routing algorithm, diameter, spanning tree, broadcasting algorithm and embedding. From the analysis, we prove that the diameter and network cost of HPN(n) are \(3\log _{10}N-1\) and \(15 \log _{10}N-1\), respectively, and it contains a spanning tree with the degree of 4. In addition, we propose link-disjoint one-to-all broadcasting algorithm and show that HPN(n) can be embedded into FP\(_k\) with expansion 1, dilation 2k and congestion 4. For most of the fixed-degree networks proposed, network cost and diameter require \(O(\sqrt{N})\) and the degree of the graph requires O(N). However, HPN(n) requires O(1) for the degree and \(O(\log _{10}N)\) for both diameter and network cost. As a result, the suggested interconnection network in this paper is superior to current fixed-degree and hierarchical networks in terms of network cost, diameter and the degree of the graph.     

Fast arithmetic in algorithmic self-assembly

In this paper we consider the time complexity of adding two n-bit numbers together within the tile self-assembly model. The (abstract) tile assembly model is a mathematical model of self-assembly in which system components are square tiles with different glue types assigned to tile edges. Assembly is driven by the attachment of singleton tiles to a growing seed assembly when the net force of glue attraction for a tile exceeds some fixed threshold. Within this frame work, we examine the time complexity of computing the sum of two n-bit numbers, where the input numbers are encoded in an initial seed assembly, and the output sum is encoded in the final, terminal assembly of the system. We show that this problem, along with multiplication, has a worst case lower bound of \(\varOmega ( \sqrt{n} )\) in 2D assembly, and \(\varOmega (\root 3 \of {n})\) in 3D assembly. We further design algorithms for both 2D and 3D that meet this bound with worst case run times of \(O(\sqrt{n})\) and \(O(\root 3 \of {n})\) respectively, which beats the previous best known upper bound of O(n). Finally, we consider average case complexity of addition over uniformly distributed n-bit strings and show how we can achieve \(O(\log n)\) average case time with a simultaneous \(O(\sqrt{n})\) worst case run time in 2D. As additional evidence for the speed of our algorithms, we implement our algorithms, along with the simpler O(n) time algorithm, into a probabilistic run-time simulator and compare the timing results.     

Close to linear space routing schemes

Let \(G=(V,E)\) be an unweighted undirected graph with n vertices and m edges, and let \(k>2\) be an integer. We present a routing scheme with a poly-logarithmic header size, that given a source s and a destination t at distance \(\varDelta \) from s, routes a message from s to t on a path whose length is \(O(k\varDelta +m^{1/k})\). The total space used by our routing scheme is \(mn^{O(1/\sqrt{\log n})}\), which is almost linear in the number of edges of the graph. We present also a routing scheme with \(n^{O(1/\sqrt{\log n})}\) header size, and the same stretch (up to constant factors). In this routing scheme, the routing table of every \(v\in V\) is at most \(kn^{O(1/\sqrt{\log n})}deg(v)\), where deg(v) is the degree of v in G. Our results are obtained by combining a general technique of Bernstein (2009), that was presented in the context of dynamic graph algorithms, with several new ideas and observations.     

A locking-free stabilized mixed finite element method for linear elasticity: the high order case

In this paper, we propose a locking-free stabilized mixed finite element method for the linear elasticity problem, which employs a jump penalty term for the displacement approximation. The continuous piecewise k-order polynomial space is used for the stress and the discontinuous piecewise \((k-1)\)-order polynomial space for the displacement, where we require that \(k\ge 3\) in the two dimensions and \(k\ge 4\) in the three dimensions. The method is proved to be stable and k-order convergent for the stress in \(H(\mathrm {div})\)-norm and for the displacement in \(L^2\)-norm. Further, the convergence does not deteriorate in the nearly incompressible or incompressible case. Finally, the numerical results are presented to illustrate the optimal convergence of the stabilized mixed method.     

Local Discontinuous Galerkin Method for Incompressible Miscible Displacement Problem in Porous Media

In this paper, we develop local discontinuous Galerkin method for the two-dimensional coupled system of incompressible miscible displacement problem. Optimal error estimates in \(L^{\infty }(0, T; L^{2})\) for concentration c, \(L^{2}(0, T; L^{2})\) for \(\nabla c\) and \(L^{\infty }(0, T; L^{2})\) for velocity \(\mathbf{u}\) are derived. The main techniques in the analysis include the treatment of the inter-element jump terms which arise from the discontinuous nature of the numerical method, the nonlinearity, and the coupling of the models. The main difficulty is how to treat the inter-element discontinuities of two independent solution variables (one from the flow equation and the other from the transport equation) at cell interfaces. Numerical experiments are shown to demonstrate the theoretical results.     

Data assimilation and sampling in Banach spaces

This paper studies the problem of approximating a function f in a Banach space \(\mathcal{X}\) from measurements \(l_j(f)\), \(j=1,\ldots ,m\), where the \(l_j\) are linear functionals from \(\mathcal{X}^*\). Quantitative results for such recovery problems require additional information about the sought after function f. These additional assumptions take the form of assuming that f is in a certain model class \(K\subset \mathcal{X}\). Since there are generally infinitely many functions in K which share these same measurements, the best approximation is the center of the smallest ball B, called the Chebyshev ball, which contains the set \(\bar{K}\) of all f in K with these measurements. Therefore, the problem is reduced to analytically or numerically approximating this Chebyshev ball. Most results study this problem for classical Banach spaces \(\mathcal{X}\) such as the \(L_p\) spaces, \(1\le p\le \infty \), and for K the unit ball of a smoothness space in \(\mathcal{X}\). Our interest in this paper is in the model classes \(K=\mathcal{K}(\varepsilon ,V)\), with \(\varepsilon >0\) and V a finite dimensional subspace of \(\mathcal{X}\), which consists of all \(f\in \mathcal{X}\) such that \(\mathrm{dist}(f,V)_\mathcal{X}\le \varepsilon \). These model classes, called approximation sets, arise naturally in application domains such as parametric partial differential equations, uncertainty quantification, and signal processing. A general theory for the recovery of approximation sets in a Banach space is given. This theory includes tight a priori bounds on optimal performance and algorithms for finding near optimal approximations. It builds on the initial analysis given in Maday et al. (Int J Numer Method Eng 102:933–965, 2015) for the case when \(\mathcal{X}\) is a Hilbert space, and further studied in Binev et al. (SIAM UQ, 2015). It is shown how the recovery problem for approximation sets is connected with well-studied concepts in Banach space theory such as liftings and the angle between spaces. Examples are given that show how this theory can be used to recover several recent results on sampling and data assimilation.     

Entanglement witness criteria of strong-<Emphasis Type="Italic">k</Emphasis>-separability for multipartite quantum states

Let \(H_{1}, H_{2},\ldots ,H_{n}\) be separable complex Hilbert spaces with \(\dim H_{i}\ge 2\) and \(n\ge 2\). Assume that \(\rho \) is a state in \(H=H_1\otimes H_2\otimes \cdots \otimes H_n\). \(\rho \) is called strong-k-separable \((2\le k\le n)\) if \(\rho \) is separable for any k-partite division of H. In this paper, an entanglement witnesses criterion of strong-k-separability is obtained, which says that \(\rho \) is not strong-k-separable if and only if there exist a k-division space \(H_{m_{1}}\otimes \cdots \otimes H_{m_{k}}\) of H, a finite-rank linear elementary operator positive on product states \(\Lambda :\mathcal {B}(H_{m_{2}}\otimes \cdots \otimes H_{m_{k}})\rightarrow \mathcal {B}(H_{m_{1}})\) and a state \(\rho _{0}\in \mathcal {S}(H_{m_{1}}\otimes H_{m_{1}})\), such that \(\mathrm {Tr}(W\rho )<0\), where \(W=(\mathrm{Id}\otimes \Lambda ^{\dagger })\rho _{0}\) is an entanglement witness. In addition, several different methods of constructing entanglement witnesses for multipartite states are also given.     

How the Hawking radiation affect quantum Fisher information of Dirac particles in the background of a Schwarzschild black hole

In this work, the effect of Hawking radiation on the quantum Fisher information (QFI) of Dirac particles is investigated in the background of a Schwarzschild black hole. Interestingly, it has been verified that the QFI with respect to the weight parameter \(\theta \) of a target state is always independent of the Hawking temperature T. This implies that if we encode the information on the weight parameter, then we can affirm that the corresponding accuracy of the parameter estimation will be immune to the Hawking effect. Besides, it reveals that the QFI with respect to the phase parameter \(\phi \) exhibits a decay behavior with the increase in the Hawking temperature T and converges to a nonzero value in the limit of infinite Hawking temperature T. Remarkably, it turns out that the function \(F_\phi \) on \(\theta =\pi \big /4\) symmetry was broken by the influence of the Hawking radiation. Finally, we generalize the case of a three-qubit system to a case of a N-qubit system, i.e., \(|\psi \rangle _{1,2,3,\ldots ,N} =(\cos \theta | 0 \rangle ^{\otimes N}+\sin \theta \mathrm{e}^{i\phi }| 1 \rangle ^{\otimes N})\) and obtain an interesting result: the number of particles in the initial state does not affect the QFI \(F_\theta \), nor the QFI \(F_\phi \). However, with the increasing number of particles located near the event horizon, \(F_\phi \) will be affected by Hawking radiation to a large extent, while \(F_\theta \) is still free from disturbance resulting from the Hawking effects.     

The Partial Fast Fourier Transform

An efficient algorithm for computing the one-dimensional partial fast Fourier transform \(f_j=\sum _{k=0}^{c(j)}e^{2\pi ijk/N} F_k\) is presented. Naive computation of the partial fast Fourier transform requires \({\mathcal O}(N^2)\) arithmetic operations for input data of length N. Unlike the standard fast Fourier transform, the partial fast Fourier transform imposes on the frequency variable k a cutoff function c(j) that depends on the space variable j; this prevents one from directly applying standard FFT algorithms. It is shown that the space–frequency domain can be partitioned into rectangular and trapezoidal subdomains over which efficient algorithms can be developed. As in the previous work of Ying and Fomel (Multiscale Model Simul 8(1):110–124, 2009), the contribution from rectangular regions can be reduced to a series of fractional-phase Fourier transforms over squares, each of which can be reduced to a convolution. In this work, we demonstrate that the partial Fourier transform over trapezoidal domains can also be reduced to a convolution. Since the computational complexity of a dealiased convolution of N inputs is \({\mathcal O}(N\log N)\), a fast algorithm for the partial Fourier transform is achieved, with a lower overall coefficient than obtained by Ying and Fomel.     

A Superconvergent HDG Method for the Maxwell Equations

We present and analyze a new hybridizable discontinuous Galerkin (HDG) method for the steady state Maxwell equations. In order to make the problem well-posed, a condition of divergence is imposed on the electric field. Then a Lagrange multiplier p is introduced, and the problem becomes the solution of a mixed curl–curl formulation of the Maxwell’s problem. We use polynomials of degree \(k+1\), k, k to approximate \({{\varvec{u}}},\nabla \times {{\varvec{u}}}\) and p respectively. In contrast, we only use a non-trivial subspace of polynomials of degree \(k+1\) to approximate the numerical tangential trace of the electric field and polynomials of degree \(k+1\) to approximate the numerical trace of the Lagrange multiplier on the faces. On the simplicial meshes, we show that the convergence rates for \(\varvec{u}\) and \(\nabla \times \varvec{u}\) are independent of the Lagrange multiplier p. If we assume the dual operator of the Maxwell equation on the domain has adequate regularity, we show that the convergence rate for \(\varvec{u}\) is \(O(h^{k+2})\). From the point of view of degrees of freedom of the globally coupled unknown: numerical trace, this HDG method achieves superconvergence for the electric field without postprocessing. Finally, we show that the superconvergence of the HDG method is also derived on general polyhedral elements. Numerical results are given to verify the theoretical analysis.     

New q-ary quantum MDS codes with distances bigger than $$\frac{ q}{2}$$

The construction of quantum MDS codes has been studied by many authors. We refer to the table in page 1482 of (IEEE Trans Inf Theory 61(3):1474–1484, 2015) for known constructions. However, there have been constructed only a few q-ary quantum MDS \([[n,n-2d+2,d]]_q\) codes with minimum distances \(d>\frac{q}{2}\) for sparse lengths \(n>q+1\). In the case \(n=\frac{q^2-1}{m}\) where \(m|q+1\) or \(m|q-1\) there are complete results. In the case \(n=\frac{q^2-1}{m}\) while \(m|q^2-1\) is neither a factor of \(q-1\) nor \(q+1\), no q-ary quantum MDS code with \(d> \frac{q}{2}\) has been constructed. In this paper we propose a direct approach to construct Hermitian self-orthogonal codes over \(\mathbf{F}_{q^2}\). Then we give some new q-ary quantum codes in this case. Moreover many new q-ary quantum MDS codes with lengths of the form \(\frac{w(q^2-1)}{u}\) and minimum distances \(d > \frac{q}{2}\) are presented.     

An interval extension of SMS method for computing weighted Moore–Penrose inverse

An interval extension of successive matrix squaring (SMS) method for computing the weighted Moore–Penrose inverse \(A^{\dagger }_{MN}\) along with its rigorous error bounds is proposed for given full rank \(m \times n\) complex matrices A, where M and N be two Hermitian positive definite matrices of orders m and n, respectively. Starting with a suitably chosen complex interval matrix containing \(A^{\dagger }_{MN}\), this method generates a sequence of complex interval matrices each enclosing \(A^{\dagger }_{MN}\) and converging to it. A new method is developed for constructing initial complex interval matrix containing \(A^{\dagger }_{MN}\). Convergence theorems are established. The R-order convergence is shown to be equal to at least l, where \(l \ge 2\). A number of numerical examples are worked out to demonstrate its efficiency and effectiveness. Graphs are plotted to show variations of the number of iterations and computational times compared to matrix dimensions. It is observed that ISMS is more stable compared to SMS.     

New quantum codes from dual-containing cyclic codes over finite rings

Let \(R=\mathbb {F}_{2^{m}}+u\mathbb {F}_{2^{m}}+\cdots +u^{k}\mathbb {F}_{2^{m}}\), where \(\mathbb {F}_{2^{m}}\) is the finite field with \(2^{m}\) elements, m is a positive integer, and u is an indeterminate with \(u^{k+1}=0.\) In this paper, we propose the constructions of two new families of quantum codes obtained from dual-containing cyclic codes of odd length over R. A new Gray map over R is defined, and a sufficient and necessary condition for the existence of dual-containing cyclic codes over R is given. A new family of \(2^{m}\)-ary quantum codes is obtained via the Gray map and the Calderbank–Shor–Steane construction from dual-containing cyclic codes over R. In particular, a new family of binary quantum codes is obtained via the Gray map, the trace map and the Calderbank–Shor–Steane construction from dual-containing cyclic codes over R.     

Adjoint-Based,Superconvergent Galerkin Approximations of Linear Functionals

We propose a new technique for computing highly accurate approximations to linear functionals in terms of Galerkin approximations. We illustrate the technique on a simple model problem, namely, that of the approximation of J(u), where \(J(\cdot )\) is a very smooth functional and u is the solution of a Poisson problem; we assume that the solution u and the solution of the adjoint problem are both very smooth. It is known that, if \(u_h\) is the approximation given by the continuous Galerkin method with piecewise polynomials of degree \(k>0\), then, as a direct consequence of its property of Galerkin orthogonality, the functional \(J(u_h)\) converges to J(u) with a rate of order \(h^{2k}\). We show how to define approximations to J(u), with a computational effort about twice of that of computing \(J(u_h)\), which converge with a rate of order \(h^{4k}\). The new technique combines the adjoint-recovery method for providing precise approximate functionals by Pierce and Giles (SIAM Rev 42(2):247–264, 2000), which was devised specifically for numerical approximations without a Galerkin orthogonality property, and the accuracy-enhancing convolution technique of Bramble and Schatz (Math Comput 31(137):94–111, 1977), which was devised specifically for numerical methods satisfying a Galerkin orthogonality property, that is, for finite element methods like, for example, continuous Galerkin, mixed, discontinuous Galerkin and the so-called hybridizable discontinuous Galerkin methods. For the latter methods, we present numerical experiments, for \(k=1,2,3\) in one-space dimension and for \(k=1,2\) in two-space dimensions, which show that \(J(u_h)\) converges to J(u) with order \(h^{2k+1}\) and that the new approximations converges with order \(h^{4k}\). The numerical experiments also indicate, for the p-version of the method, that the rate of exponential convergence of the new approximations is about twice that of \(J(u_h)\).     

Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms

The Planar Feedback Vertex Set problem asks whether an n-vertex planar graph contains at most k vertices meeting all its cycles. The Face Cover problem asks whether all vertices of a plane graph G lie on the boundary of at most k faces of G. Standard techniques from parameterized algorithm design indicate that both problems can be solved by sub-exponential parameterized algorithms (where k is the parameter). In this paper we improve the algorithmic analysis of both problems by proving a series of combinatorial results relating the branchwidth of planar graphs with their face cover. Combining this fact with duality properties of branchwidth, allows us to derive analogous results on feedback vertex set. As a consequence, it follows that Planar Feedback Vertex Set and Face Cover can be solved in \(O(2^{15.11\cdot\sqrt{k}}+n^{2})\) and \(O(2^{10.1\cdot\sqrt {k}}+n^{2})\) steps, respectively.     

Robust quantum spatial search

Quantum spatial search has been widely studied with most of the study focusing on quantum walk algorithms. We show that quantum walk algorithms are extremely sensitive to systematic errors. We present a recursive algorithm which offers significant robustness to certain systematic errors. To search N items, our recursive algorithm can tolerate errors of size \(O(1{/}\sqrt{\ln N})\) which is exponentially better than quantum walk algorithms for which tolerable error size is only \(O(\ln N{/}\sqrt{N})\). Also, our algorithm does not need any ancilla qubit. Thus our algorithm is much easier to implement experimentally compared to quantum walk algorithms.     

High-Order Compact Difference Methods for Caputo-Type Variable Coefficient Fractional Sub-diffusion Equations in Conservative Form

A set of high-order compact finite difference methods is proposed for solving a class of Caputo-type fractional sub-diffusion equations in conservative form. The diffusion coefficient of the equation may be spatially variable, and the proposed methods have the global convergence order \(\mathcal{O}(\tau ^{r}+h^{4})\), where \(r\ge 2\) is a positive integer and \(\tau \) and h are the temporal and spatial steps. Such new high-order compact difference methods greatly improve the known methods in the literature. The local truncation error and the solvability of the methods are discussed in detail. By applying a discrete energy technique to the matrix form of the methods, a rigorous theoretical analysis of the stability and convergence of the methods is carried out for the case of \(2\le r\le 6\), and the optimal error estimates in the weighted \(H^{1}\), \(L^{2}\) and \(L^{\infty }\) norms are obtained for the general case of variable coefficient. Applications are given to two model problems, and some numerical results are presented to illustrate the various convergence orders of the methods.