Multigrid Convergence for the MDCA Curvature Estimator

We consider the problem of estimating the curvature profile along the boundaries of digital objects in segmented black-and-white images. We start with the curvature estimator proposed by Roussillon et al. which is based on the calculation of maximal digital circular arcs (MDCAs). We extend this estimator to the \(\lambda \)-MDCA curvature estimator that considers several MDCAs for each boundary pixel and is therefore smoother than the classical MDCA curvature estimator. We prove an explicit order of convergence result for convex subsets in \(\mathbb {R}^2\) with positive, continuous curvature profile. In addition, we evaluate the curvature estimator on various objects with known curvature profile. We show that the observed order of convergence is close to the theoretical limit of \(\mathcal {O}\left( h^{\frac{1}{3}}\right) \) as \(h\rightarrow 0^+\). Furthermore, we establish that the \(\lambda \)-MDCA curvature estimator outperforms the MDCA curvature estimator, especially in the neighborhood of corners.     

A family of admissible heuristics for A* to perform inference in probabilistic classifier chains

Probabilistic classifier chains have recently gained interest in multi-label classification, due to their ability to optimally estimate the joint probability of a set of labels. The main hindrance is the excessive computational cost of performing inference in the prediction stage. This pitfall has opened the door to propose efficient inference alternatives that avoid exploring all the possible solutions. The \(\epsilon \)-approximate algorithm, beam search and Monte Carlo sampling are appropriate techniques, but only \(\epsilon \)-approximate algorithm with \(\epsilon =0\) theoretically guarantees reaching an optimal solution in terms of subset 0/1 loss. This paper offers another alternative based on heuristic search that keeps such optimality. It consists of applying the A* algorithm providing an admissible heuristic able to explore fewer nodes than the \(\epsilon \)-approximate algorithm with \(\epsilon =0\). A preliminary study has already coped with this goal, but at the expense of the high computational time of evaluating the heuristic and only for linear models. In this paper, we propose a family of heuristics defined by a parameter that controls the trade-off between the number of nodes explored and the cost of computing the heuristic. Besides, a certain value of the parameter provides a method that is also suitable for the non-linear case. The experiments reported over several benchmark datasets show that the number of nodes explored remains quite steady for different values of the parameter, although the time considerably increases for high values. Hence, low values of the parameter give heuristics that theoretically guarantee exploring fewer nodes than the \(\epsilon \)-approximate algorithm with \(\epsilon =0\) and show competitive computational time. Finally, the results exhibit the good behavior of the A* algorithm using these heuristics in complex situations such as the presence of noise.     

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 \).     

Engineering design optimization using an improved local search based epsilon differential evolution algorithm

Many engineering problems can be categorized into constrained optimization problems (COPs). The engineering design optimization problem is very important in engineering industries. Because of the complexities of mathematical models, it is difficult to find a perfect method to solve all the COPs very well. \(\varepsilon \) constrained differential evolution (\(\varepsilon \)DE) algorithm is an effective method in dealing with the COPs. However, \(\varepsilon \)DE still cannot obtain more precise solutions. The interaction between feasible and infeasible individuals can be enhanced, and the feasible individuals can lead the population finding optimum around it. Hence, in this paper we propose a new algorithm based on \(\varepsilon \) feasible individuals driven local search called as \(\varepsilon \) constrained differential evolution algorithm with a novel local search operator (\(\varepsilon \)DE-LS). The effectiveness of the proposed \(\varepsilon \)DE-LS algorithm is tested. Furthermore, four real-world engineering design problems and a case study have been studied. Experimental results show that the proposed algorithm is a very effective method for the presented engineering design optimization problems.     

Robust Parametric Twin Support Vector Machine for Pattern Classification

In this paper, we propose a robust parametric twin support vector machine (RPTWSVM) classifier based on Parametric-\(\nu \)-Support Vector Machine (Par-\(\nu \)-SVM) and twin support vector machine. In order to capture heteroscedastic noise present in the training data, RPTWSVM finds a pair of parametric margin hyperplanes that automatically adjusts the parametric insensitive margin to incorporate the structural information of data. The proposed model of RPTWSVM is not only useful in controlling the heteroscedastic noise but also has much faster training speed when compared to Par-\(\nu \)-SVM. Experimental results on several machine learning benchmark datasets show the advantages of RPTWSVM both in terms of generalization ability and training speed over other related models.     

Involutive method for computing Gröbner bases over $$ \mathbb{F}_2 $$

In this paper, an involutive algorithm for computation of Gröbner bases for polynomial ideals in a ring of polynomials in many variables over the finite field \(\mathbb{F}_2 \) with the values of variables belonging of \(\mathbb{F}_2 \) is considered. The algorithm uses Janet division and is specialized for a graded reverse lexicographical order of monomials. We compare efficiency of this algorithm and its implementation in C++ with that of the Buchberger algorithm, as well as with the algorithms of computation of Gröbner bases that are built in the computer algebra systems Singular and CoCoA and in the FGb library for Maple. For the sake of comparison, we took widely used examples of computation of Gröbner bases over ? and adapted them for \(\mathbb{F}_2 \). Polynomial systems over \(\mathbb{F}_2 \) with the values of variables in \(\mathbb{F}_2 \) are of interest, in particular, for modeling quantum computation and a number of cryptanalysis problems.     

Pure state ‘really’ informationally complete with rank-1 POVM

What is the minimal number of elements in a rank-1 positive operator-valued measure (POVM) which can uniquely determine any pure state in d-dimensional Hilbert space \(\mathcal {H}_d\)? The known result is that the number is no less than \(3d-2\). We show that this lower bound is not tight except for \(d=2\) or 4. Then we give an upper bound \(4d-3\). For \(d=2\), many rank-1 POVMs with four elements can determine any pure states in \(\mathcal {H}_2\). For \(d=3\), we show eight is the minimal number by construction. For \(d=4\), the minimal number is in the set of \(\{10,11,12,13\}\). We show that if this number is greater than 10, an unsettled open problem can be solved that three orthonormal bases cannot distinguish all pure states in \(\mathcal {H}_4\). For any dimension d, we construct \(d+2k-2\) adaptive rank-1 positive operators for the reconstruction of any unknown pure state in \(\mathcal {H}_d\), where \(1\le k \le d\).     

$$\mathcal $$-FAINV: hierarchically factored approximate inverse preconditioners

Given a sparse matrix, its LU-factors, inverse and inverse factors typically suffer from substantial fill-in, leading to non-optimal complexities in their computation as well as their storage. In the past, several computationally efficient methods have been developed to compute approximations to these otherwise rather dense matrices. Many of these approaches are based on approximations through sparse matrices, leading to well-known ILU, sparse approximate inverse or factored sparse approximate inverse techniques and their variants. A different approximation approach is based on blockwise low rank approximations and is realized, for example, through hierarchical (\(\mathcal H\)-) matrices. While \(\mathcal H\)-inverses and \(\mathcal H\)-LU factors have been discussed in the literature, this paper will consider the construction of an approximation of the factored inverse through \(\mathcal H\)-matrices (\(\mathcal H\)-FAINV). We will describe a blockwise approach that permits to replace (exact) matrix arithmetic through approximate efficient \(\mathcal H\)-arithmetic. We conclude with numerical results in which we use approximate factored inverses as preconditioners in the iterative solution of the discretized convection–diffusion problem.     

High Order Algorithm for the Time-Tempered Fractional Feynman–Kac Equation

We provide and analyze the high order algorithms for the model describing the functional distributions of particles performing anomalous motion with power-law jump length and tempered power-law waiting time. The model is derived in Wu et al. (Phys Rev E 93:032151, 2016), being called the time-tempered fractional Feynman–Kac equation named after Richard Feynman and Mark Kac who first considered the model describing the functional distribution of normal motion. The key step of designing the algorithms is to discretize the time tempered fractional substantial derivative, being defined as

$$\begin{aligned} {^S\!}D_t^{\gamma ,\widetilde{\lambda }} G(x,p,t)\!=\!D_t^{\gamma ,\widetilde{\lambda }} G(x,p,t)\!-\!\lambda ^\gamma G(x,p,t) \end{aligned}$$

with \(\widetilde{\lambda }=\lambda + pU(x),\, p=\rho +J\eta ,\, J=\sqrt{-1}\), where

$$\begin{aligned} D_t^{\gamma ,\widetilde{\lambda }} G(x,p,t) =\frac{1}{\varGamma (1-\gamma )} \left[ \frac{\partial }{\partial t}+\widetilde{\lambda } \right] \int _{0}^t{\left( t-z\right) ^{-\gamma }}e^{-\widetilde{\lambda }\cdot (t-z)}{G(x,p,z)}dz, \end{aligned}$$

and \(\lambda \ge 0\), \(0<\gamma <1\), \(\rho >0\), and \(\eta \) is a real number. The designed schemes are unconditionally stable and have the global truncation error \(\mathscr {O}(\tau ^2+h^2)\), being theoretically proved and numerically verified in complex space. Moreover, some simulations for the distributions of the first passage time are performed, and the second order convergence is also obtained for solving the ‘physical’ equation (without artificial source term).

     

A stochastic framework for K-SVD with applications on face recognition

In recent years, the sparse representation modeling of signals has received a lot of attention due to its state-of-the-art performance in different computer vision tasks. One important factor to its success is the ability to promote representations that are well adapted to the data. This is achieved by the use of dictionary learning algorithms. The most well known of these algorithms is K-SVD. In this paper, we propose a stochastic framework for K-SVD called \(\alpha\)K-SVD. The \(\alpha\)K-SVD uses a parameter \(\alpha\) to control a compromise between exploring the space of dictionaries and improving a possible solution. The use of this heuristic search strategy was motivated by the fact that K-SVD uses a greedy search algorithm with fast convergence, possibly leading to local minimum. Our approach is evaluated on two public face recognition databases. The results show that our approach yields better results than K-SVD and LC-KSVD (a K-SVD adaptation to classification) when the sparsity level is low.     

Monogamy and polygamy for multi-qubit W-class states using convex-roof extended negativity of assistance and Rényi-$$\alpha $$ entropy

We present some new analytical polygamy inequalities satisfied by the x-th power of convex-roof extended negativity of assistance with \(x\ge 2\) and \(x\le 0\) for multi-qubit generalized W-class states. Using Rényi-\(\alpha \) entropy (R\(\alpha \)E) with \(\alpha \in [(\sqrt{7}-1)/2, (\sqrt{13}-1)/2]\), we prove new monogamy and polygamy relations. We further show that the monogamy inequality also holds for the \(\mu \)th power of Rényi-\(\alpha \) entanglement. Moreover, we study two examples in multipartite higher-dimensional system for those new inequalities.     

Unconditionally Optimal Error Analysis of Crank–Nicolson Galerkin FEMs for a Strongly Nonlinear Parabolic System

In this paper, we present unconditionally optimal error estimates of linearized Crank–Nicolson Galerkin finite element methods for a strongly nonlinear parabolic system in \(\mathbb {R}^d\ (d=2,3)\). However, all previous works required certain time-step conditions that were dependent on the spatial mesh size. In order to overcome several entitative difficulties caused by the strong nonlinearity of the system, the proof takes two steps. First, by using a temporal-spatial error splitting argument and a new technique, optimal \(L^2\) error estimates of the numerical schemes can be obtained under the condition \(\tau \ge h\), where \(\tau \) denotes the time-step size and h is the spatial mesh size. Second, we obtain the boundedness of numerical solutions by mathematical induction and inverse inequality when \(\tau \le h\). Then, optimal \(L^2\) and \(H^1\) error estimates are proved in a different way for such case. Numerical results are given to illustrate our theoretical analyses.     

From LTL to deterministic automata

We present a new algorithm to construct a (generalized) deterministic Rabin automaton for an LTL formula \(\varphi \). The automaton is the product of a co-Büchi automaton for \(\varphi \) and an array of Rabin automata, one for each \({\mathbf {G}}\)-subformula of \(\varphi \). The Rabin automaton for \({\mathbf {G}}\psi \) is in charge of recognizing whether \({\mathbf {F}}{\mathbf {G}}\psi \) holds. This information is passed to the co-Büchi automaton that decides on acceptance. As opposed to standard procedures based on Safra’s determinization, the states of all our automata have a clear logical structure, which allows for various optimizations. Experimental results show improvement in the sizes of the resulting automata compared to existing methods.     

The local–global conjecture for scheduling with non-linear cost

We consider the classical scheduling problem on a single machine, on which we need to schedule sequentially n given jobs. Every job j has a processing time \(p_j\) and a priority weight \(w_j\), and for a given schedule a completion time \(C_j\). In this paper, we consider the problem of minimizing the objective value \(\sum _j w_j C_j^\beta \) for some fixed constant \(\beta >0\). This non-linearity is motivated for example by the learning effect of a machine improving its efficiency over time, or by the speed scaling model. For \(\beta =1\), the well-known Smith’s rule that orders job in the non-increasing order of \(w_j/p_j\) gives the optimum schedule. However, for \(\beta \ne 1\), the complexity status of this problem is open. Among other things, a key issue here is that the ordering between a pair of jobs is not well defined, and might depend on where the jobs lie in the schedule and also on the jobs between them. We investigate this question systematically and substantially generalize the previously known results in this direction. These results lead to interesting new dominance properties among schedules which lead to huge speed up in exact algorithms for the problem. An experimental study evaluates the impact of these properties on the exact algorithm A*.     

Counter machines and crystallographic structures

One way to depict a crystallographic structure is by a periodic (di)graph, i.e., a graph whose group of automorphisms has a translational subgroup of finite index acting freely on the structure. We establish a relationship between periodic graphs representing crystallographic structures and an infinite hierarchy of intersection languages \(\mathcal {DCL}_d,\,d=0,1,2,\ldots \), within the intersection classes of deterministic context-free languages. We introduce a class of counter machines that accept these languages, where the machines with d counters recognize the class \(\mathcal {DCL}_d\). An intersection of d languages in \(\mathcal {DCL}_1\) defines \(\mathcal {DCL}_d\). We prove that there is a one-to-one correspondence between sets of walks starting and ending in the same unit of a d-dimensional periodic (di)graph and the class of languages in \(\mathcal {DCL}_d\). The proof uses the following result: given a digraph \(\Delta \) and a group G, there is a unique digraph \(\Gamma \) such that \(G\le \mathrm{Aut}\,\Gamma ,\,G\) acts freely on the structure, and \(\Gamma /G \cong \Delta \).     

A Neumann series of Bessel functions representation for solutions of Sturm–Liouville equations

A Neumann series of Bessel functions (NSBF) representation for solutions of Sturm–Liouville equations and for their derivatives is obtained. The representation possesses an attractive feature for applications: for all real values of the spectral parameter \(\omega \) the estimate of the difference between the exact solution and the approximate one (the truncated NSBF) depends on N (the truncation parameter) and the coefficients of the equation and does not depend on \(\omega \). A similar result is valid when \(\omega \in {\mathbb {C}}\) belongs to a strip \(\left| \hbox {Im }\omega \right| <C\). This feature makes the NSBF representation especially useful for applications requiring computation of solutions for large intervals of \(\omega \). Error and decay rate estimates are obtained. An algorithm for solving initial value, boundary value or spectral problems for the Sturm–Liouville equation is developed and illustrated on a test problem.     

Flexible bandwidth assignment with application to optical networks

We introduce two scheduling problems, the flexible bandwidth allocation problem (\(\textsc {FBAP}\)) and the flexible storage allocation problem (\(\textsc {FSAP}\)). In both problems, we have an available resource, and a set of requests, each consists of a minimum and a maximum resource requirement, for the duration of its execution, as well as a profit accrued per allocated unit of the resource. In \(\textsc {FBAP}\), the goal is to assign the available resource to a feasible subset of requests, such that the total profit is maximized, while in \(\textsc {FSAP}\) we also require that each satisfied request is given a contiguous portion of the resource. Our problems generalize the classic bandwidth allocation problem (BAP) and storage allocation problem (SAP) and are therefore \(\text {NP-hard}\). Our main results are a 3-approximation algorithm for \(\textsc {FBAP}\) and a \((3+\epsilon )\)-approximation algorithm for \(\textsc {FSAP}\), for any fixed \(\epsilon >0 \). These algorithms make nonstandard use of the local ratio technique. Furthermore, we present a \((2+\epsilon )\)-approximation algorithm for \(\textsc {SAP}\), for any fixed \(\epsilon >0 \), thus improving the best known ratio of \(\frac{2e-1}{e-1} + \epsilon \). Our study is motivated also by critical resource allocation problems arising in all-optical networks.     

Decoupled,Unconditionally Stable,Higher Order Discretizations for MHD Flow Simulation

We propose, analyze, and test a new MHD discretization which decouples the system into two Oseen problems at each timestep yet maintains unconditional stability with respect to the time step size, is optimally accurate in space, and behaves like second order in time in practice. The proposed method chooses a parameter \(\theta \in [0,1]\), dependent on the viscosity \(\nu \) and magnetic diffusivity \(\nu _m\), so that the explicit treatment of certain viscous terms does not cause instabilities, and gives temporal accuracy \(O(\Delta t^2 + (1-\theta )|\nu -\nu _m|\Delta t)\). In practice, \(\nu \) and \(\nu _m\) are small, and so the method behaves like second order. When \(\theta =1\), the method reduces to a linearized BDF2 method, but it has been proven by Li and Trenchea that such a method is stable only in the uncommon case of \(\frac{1}{2}< \frac{\nu }{\nu _m} < 2\). For the proposed method, stability and convergence are rigorously proven for appropriately chosen \(\theta \), and several numerical tests are provided that confirm the theory and show the method provides excellent accuracy in cases where usual BDF2 is unstable.     

Compatibility of observables on effect algebras

We compare different notions of simultaneous measurability (compatibility) of observables on lattice \(\sigma \)-effect algebras and more generally, on \(\sigma \)-effect algebras that can be covered by \(\sigma \)-MV-algebras. We prove that every \(\sigma \)-MV-algebra is the range of a \(\sigma \)-additive observable, and we compare the following notions of compatibility of observables: joint measurability, coexistence, joint measurability of binarizations, coexistence of binarizations, smearings of the same observable. We prove that if there is a faithful state on the effect algebra, then any two standard observables that are smearings of the same (sharp) observable admit a generalized joint observable.