Optimization with Respect to Order in a Fractional Diffusion Model: Analysis,Approximation and Algorithmic Aspects

We consider an identification (inverse) problem, where the state \({\mathsf {u}}\) is governed by a fractional elliptic equation and the unknown variable corresponds to the order \(s \in (0,1)\) of the underlying operator. We study the existence of an optimal pair \(({\bar{s}}, {{\bar{{\mathsf {u}}}}})\) and provide sufficient conditions for its local uniqueness. We develop semi-discrete and fully discrete algorithms to approximate the solutions to our identification problem and provide a convergence analysis. We present numerical illustrations that confirm and extend our theory.     

Automatic microstructural characterization and classification using probabilistic neural network on ultrasound signals

During the gas tungsten arc welding of nickel based superalloys, the secondary phases such as Laves and carbides are formed in final stage of solidification. But, other phases such as \(\gamma ^{{\prime \prime }}\) and \(\delta \) phases can precipitate in the microstructure, during aging at high temperatures. However, it is possible to minimize the formation of the Nb-rich Laves phases and therefore reduce the possibility of solidification cracking by adopting the appropriate welding conditions. This paper aims at the automatic microstructurally characterizing the kinetics of phase transformations on an Nb-base alloy, thermally aged at 650 and 950  \(^{\circ }\)C for 10, 100 and 200 h, through backscattered ultrasound signals at frequency of 4 MHz. The ultrasound signals are inherently non-linear and thus the conventional linear time and frequency domain methods can not reveal the complexity of these signals clearly. Consequently, an automated processing system is designed using the higher-order statistics techniques, such as 3rd-order cumulant and bispectrum. These techniques are non-linear methods which are highly robust to noise. For this, the coefficients of 3rd-order cumulant and bispectrum of ultrasound signals are subjected to the independent component analysis (ICA) technique to reduce the statistical redundancy and reveal discriminating features. These dimensionality reduced features are fed to the probabilistic neural network (PNN) to automatic microstructural classification. The training process of PNN depends only on the selection of the smoothing parameters of pattern neurons. In this article, we propose the application of the bees algorithm to the automatic adaptation of smoothing parameters. The ICA components of cumulant coefficients coupled with the optimized PNN yielded the highest average accuracy of 97.0 and 83.5 %, respectively for thermal aging at 650 and 950 \(^{\circ }\)C. Thus, the proposed processing system provides high reliability to be used for microstructure characterization through ultrasound signals.     

A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines,small looseness,and small slack

We study the problem of non-preemptively scheduling n jobs, each job j with a release time \(t_j\), a deadline \(d_j\), and a processing time \(p_j\), on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints \(|d_j-t_j|\le \lambda {}p_j\) and \(|d_j-t_j|\le p_j +\sigma \) and showed the problem to be NP-hard for any \(\lambda >1\) and for any \(\sigma \ge 2\). We complement their results by parameterized complexity studies: we show that, for any \(\lambda >1\), the problem remains weakly NP-hard even for \(m=2\) and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and \(\lambda \) and a fixed-parameter tractability result for the parameter m combined with \(\sigma \).     

Construction of quantum caps in projective space <Emphasis Type="Italic">PG</Emphasis>(<Emphasis Type="Italic">r</Emphasis>, 4) and quantum codes of distance 4

Constructions of quantum caps in projective space PG(r, 4) by recursive methods and computer search are discussed. For each even n satisfying \(n\ge 282\) and each odd z satisfying \(z\ge 275\), a quantum n-cap and a quantum z-cap in \(PG(k-1, 4)\) with suitable k are constructed, and \([[n,n-2k,4]]\) and \([[z,z-2k,4]]\) quantum codes are derived from the constructed quantum n-cap and z-cap, respectively. For \(n\ge 282\) and \(n\ne 286\), 756 and 5040, or \(z\ge 275\), the results on the sizes of quantum caps and quantum codes are new, and all the obtained quantum codes are optimal codes according to the quantum Hamming bound. While constructing quantum caps, we also obtain many large caps in PG(r, 4) for \(r\ge 11\). These results concerning large caps provide improved lower bounds on the maximal sizes of caps in PG(r, 4) for \(r\ge 11\).     

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.     

A dual-axis MEMS capacitive inertial sensor with high-density proof mass

This paper reports a novel dual-axis microelectromechanical systems (MEMS) capacitive inertial sensor that utilizes multi-layered electroplated gold. All the MEMS structures are made by gold electroplating that is used as a post complementary metal-oxide semiconductor (CMOS) process. Due to the high density of gold, the Brownian noise on the proof mass becomes lower than those made of other materials such as silicon in the same size. The single gold proof mass works as a dual-axis sensing electrode by utilizing both out-of-plane (Z axis) and in-plane (X axis) motions; the proof mass has been designed to be 660 μm × 660 μm in area with the thickness of 12 μm, and the actual Brownian noise in the proof mass has been measured to be 1.2 \({\upmu}{\text{G/}}\sqrt {\text{Hz}}\) (in Z axis) and 0.29 \({\upmu}{\text{G/}}\sqrt {\text{Hz}}\) (in X axis) at room temperature, where 1 G = 9.8 m/s². The miniaturized dual-axis MEMS accelerometer can be implemented in integrated CMOS-MEMS accelerometers to detect a broad range of acceleration with sub-1G resolution on a single sensor chip.     

Mutually unbiased maximally entangled bases in $$\mathbb {C}^d\otimes \mathbb {C}^d$$

We study mutually unbiased maximally entangled bases (MUMEB’s) in bipartite system \(\mathbb {C}^d\otimes \mathbb {C}^d (d \ge 3)\). We generalize the method to construct MUMEB’s given in Tao et al. (Quantum Inf Process 14:2291–2300, 2015), by using any commutative ring R with d elements and generic character of \((R,+)\) instead of \(\mathbb {Z}_d=\mathbb {Z}/d\mathbb {Z}\). Particularly, if \(d=p_1^{a_1}p_2^{a_2}\ldots p_s^{a_s}\) where \(p_1, \ldots , p_s\) are distinct primes and \(3\le p_1^{a_1}\le \cdots \le p_s^{a_s}\), we present \(p_1^{a_1}-1\) MUMEB’s in \(\mathbb {C}^d\otimes \mathbb {C}^d\) by taking \(R=\mathbb {F}_{p_1^{a_1}}\oplus \cdots \oplus \mathbb {F}_{p_s^{a_s}}\), direct sum of finite fields (Theorem 3.3).     

A linear-time algorithm for finding Hamiltonian (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-paths in odd-sized rectangular grid graphs with a rectangular hole

A grid graph \(G_{\mathrm{g}}\) is a finite vertex-induced subgraph of the two-dimensional integer grid \(G^\infty \). A rectangular grid graph R(m, n) is a grid graph with horizontal size m and vertical size n. A rectangular grid graph with a rectangular hole is a rectangular grid graph R(m, n) such that a rectangular grid subgraph R(k, l) is removed from it. The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give necessary conditions for the existence of a Hamiltonian path between two given vertices in an odd-sized rectangular grid graph with a rectangular hole. In addition, we show that how such paths can be computed in linear time.     

Exact exponential algorithms for 3-machine flowshop scheduling problems

In this paper, we focus on the design of an exact exponential time algorithm with a proved worst-case running time for 3-machine flowshop scheduling problems considering worst-case scenarios. For the minimization of the makespan criterion, a Dynamic Programming algorithm running in \({\mathcal {O}}^*(3^n)\) is proposed, which improves the current best-known time complexity \(2^{{\mathcal {O}}(n)}\times \Vert I\Vert ^{{\mathcal {O}}(1)}\) in the literature. The idea is based on a dominance condition and the consideration of the Pareto Front in the criteria space. The algorithm can be easily generalized to other problems that have similar structures. The generalization on two problems, namely the \(F3\Vert f_\mathrm{max}\) and \(F3\Vert \sum f_i\) problems, is discussed.     

Flow-induced deformation of compliant microchannels and its effect on pressure–flow characteristics

We report theoretical and experimental investigations of flow through compliant microchannels in which one of the walls is a thin PDMS membrane. A theoretical model is derived that provides an insight into the physics of the coupled fluid–structure interaction. For a fixed channel size, flow rate and fluid viscosity, a compliance parameter \(f_{\text{p}}\) is identified, which controls the pressure–flow characteristics. The pressure and deflection profiles and pressure–flow characteristics of the compliant microchannels are predicted using the model and compared with experimental data, which show good agreement. The pressure–flow characteristics of the compliant microchannel are compared with that obtained for an identical conventional (rigid) microchannel. For a fixed channel size and flow rate, the effect of fluid viscosity and compliance parameter \(f_{\text{p}}\) on the pressure drop is predicted using the theoretical model, which successfully confront experimental data. The pressure–flow characteristics of a non-Newtonian fluid (0.1 % polyethylene oxide solution) through the compliant and conventional (rigid) microchannels are experimentally measured and compared. The results reveal that for a given change in the flow rate, the corresponding modification in the viscosity due to the shear thinning effect determines the change in the pressure drop in such microchannels.     

The remote set problem on lattices

We initiate studying the Remote Set Problem (\({\mathsf{RSP}}\)) on lattices, which given a lattice asks to find a set of points containing a point which is far from the lattice. We show a polynomial-time deterministic algorithm that on rank n lattice \({\mathcal{L}}\) outputs a set of points, at least one of which is \({\sqrt{\log n / n} \cdot \rho(\mathcal{L})}\) -far from \({\mathcal{L}}\) , where \({\rho(\mathcal{L})}\) stands for the covering radius of \({\mathcal{L}}\) (i.e., the maximum possible distance of a point in space from \({\mathcal{L}}\)). As an application, we show that the covering radius problem with approximation factor \({\sqrt{n / \log n}}\) lies in the complexity class \({\mathsf{NP}}\) , improving a result of Guruswami et al. (Comput Complex 14(2): 90–121, 2005) by a factor of \({\sqrt{\log n}}\) .Our results apply to any \({\ell_p}\) norm for \({2 \leq p \leq \infty}\) with the same approximation factors (except a loss of \({\sqrt{\log \log n}}\) for \({p = \infty}\)). In addition, we show that the output of our algorithm for \({\mathsf{RSP}}\) contains a point whose \({\ell_2}\) distance from \({\mathcal{L}}\) is at least \({(\log n/n)^{1/p} \cdot \rho^{(p)}(\mathcal{L})}\) , where \({\rho^{(p)}(\mathcal{L})}\) is the covering radius of \({\mathcal{L}}\) measured with respect to the \({\ell_p}\) norm. The proof technique involves a theorem on balancing vectors due to Banaszczyk (Random Struct Algorithms 12(4):351–360, 1998) and the “six standard deviations” theorem of Spencer (Trans Am Math Soc 289(2):679–706, 1985).     

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.     

Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets

Using quantum annealing to solve an optimization problem requires minor embedding a logic graph into a known hardware graph. In an effort to reduce the complexity of the minor embedding problem, we introduce the minor set cover (MSC) of a known graph \({\mathcal {G}}\): a subset of graph minors which contain any remaining minor of the graph as a subgraph. Any graph that can be embedded into \({\mathcal {G}}\) will be embeddable into a member of the MSC. Focusing on embedding into the hardware graph of commercially available quantum annealers, we establish the MSC for a particular known virtual hardware, which is a complete bipartite graph. We show that the complete bipartite graph \(K_{N,N}\) has a MSC of N minors, from which \(K_{N+1}\) is identified as the largest clique minor of \(K_{N,N}\). The case of determining the largest clique minor of hardware with faults is briefly discussed but remains an open question.     

Fabrication and integration of microscale permanent magnets for particle separation in microfluidics

Microfluidic magnetophoresis is an effective technique to separate magnetically labeled bioconjugates in lab-on-a-chip applications. However, it is challenging and expensive to fabricate and integrate microscale permanent magnets into microfluidic devices with conventional methods that use thin-film deposition and lithography. Here, we propose and demonstrate a simple and low-cost technique to fabricate microscale permanent magnetic microstructures and integrate them into microfluidic devices. In this method, microstructure channels were fabricated next to a microfluidic channel and were injected with a liquid mixture of neodymium (NdFeB) powders and polydimethylsiloxane (PDMS). After the mixture was cured, the resulted solid NdFeB–PDMS microstructure was permanently magnetized to form microscale magnets. The microscale magnets generate strong magnetic forces capable of separating magnetic particles in microfluidic channels. Systematic experiments and numerical simulations were conducted to study the geometric effects of the microscale magnets. It was found that rectangular microscale magnets generate larger \(({\mathbf {H}}\cdot \nabla ) {\mathbf {H}}\) which is proportional to magnetic force and have a wider range of influence than the semicircle or triangle magnets. For multiple connected rectangular microscale magnet, additional geometric parameters, including separation distance, height and width of the individual elements, further influence the particle separation and were characterized experimentally. With an optimal size combination, complete separation of yeast cells and magnetic microparticles of similar sizes (\(4\;\upmu \hbox {m}\)) was demonstrated with the multi-rectangular magnet microfluidic device.     

An EMG-marker tracking optimisation method for estimating muscle forces

Existing algorithms for estimating muscle forces mainly use least-activation criteria, which do not necessarily lead to physiologically consistent results. Our objective was to assess an innovative forward dynamics-based optimisation, assisted by both electromyography (EMG) and marker tracking, for estimating the upper-limb muscle forces. A reference movement was generated, and EMG was simulated to reproduce the desired joint kinematics. Random noise was added to both simulated EMG and marker trajectories in order to create 30 trials. Then, muscle forces were estimated using (1) the innovative EMG-marker tracking forward optimisation, (2) a marker tracking forward optimisation with a least-excitation criterion, and (3) static optimisation with a least-activation criterion. Approaches (1) and (2) were solved using a direct multiple shooting algorithm. Finally, reference and estimated joint angles and muscle forces for the three optimisations were statistically compared using root-mean-square errors (RMSEs), biases, and statistical parametric mapping. The joint angles RMSEs were qualitatively similar across the three optimisations: (1) \(1.63 \pm 0.51\)°; (2) \(2.02 \pm 0.64\)°; (3) \(0.79 \pm 0.38\)°. However, the muscle forces RMSE for the EMG-marker tracking optimisation (\(20.39 \pm 13.24\) N) was about seven times smaller than those resulting from the marker tracking (\(124.22 \pm 118.22\) N) and static (\(148.15 \pm 94.01\) N) optimisations. The originality of this novel approach is close tracking of both simulated EMG and marker trajectories in the same objective function, using forward dynamics. Therefore, the presented EMG-marker tracking optimisation led to accurate muscle forces estimations.     

Temperley–Lieb algebra,Yang-Baxterization and universal gate

A method of constructing n ² × n ² matrix realization of Temperley–Lieb algebras is presented. The single loop of these realizations are \({d=\sqrt{n}}\). In particular, a 9 × 9-matrix realization with single loop \({d=\sqrt{3}}\) is discussed. A unitary Yang–Baxter \({\breve{R}\theta,q_{1},q_{2})}\) matrix is obtained via the Yang-Baxterization process. The entanglement properties and geometric properties (i.e., Berry Phase) of this Yang–Baxter system are explored.     

Global Stability of a Discrete Population Dynamics Model with Two Delays

A population dynamics model \(x_n = \frac{{\alpha x_{n - m} }}{{1 + x_{n - m} + \beta x_{n - k} }}\) with two delays k and m and coefficients α > 1 and β ≥ 0 is studied. A sufficient condition, which is also necessary for certain delays, for the global asymptotic stability of the stationary solution \(x_n = \frac{{\alpha - 1}}{{\beta + 1}}\) is formulated.     

Automatic Task-Based Code Generation for High Performance Domain Specific Embedded Language

Providing high level tools for parallel programming while sustaining a high level of performance has been a challenge that techniques like Domain Specific Embedded Languages try to solve. In previous works, we investigated the design of such a DSEL—NT\(^2\)—providing a Matlab -like syntax for parallel numerical computations inside a C++ library. In this paper, we show how NT\(^2\!\) has been redesigned for shared memory systems in an extensible and portable way. The new NT\(^2\!\) design relies on a tiered Parallel Skeleton system built using asynchronous task management and automatic compile-time taskification of user level code. We describe how this system can operate various shared memory runtimes and evaluate the design by using two benchmarks implementing linear algebra algorithms.