On the minimum of a positive polynomial over the standard simplex

We present a new positive lower bound for the minimum value taken by a polynomial P$P$ with integer coefficients in k$k$ variables over the standard simplex of R^k${\mathbb{R}}^k$, assuming that P$P$ is positive on the simplex. This bound depends only on the number of variables k$k$, the degree d$d$ and the bitsize τ$\tau$ of the coefficients of P$P$ and improves all the previous bounds for arbitrary polynomials which are positive over the simplex.     

A linear-time 2-approximation algorithm for the watchman route problem for simple polygons

Given a simple polygon P$P$ of n$n$ vertices, the watchman route problem   asks for a shortest (closed) route inside P$P$ such that each point in the interior of P$P$ can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most two times that of the shortest watchman route. The best known algorithm for computing a shortest watchman route takes O(n⁴logn)$O(n^{4}logn)$ time, which is too complicated to be suitable in practice.     

Finite derivation type for Rees matrix semigroups

This paper introduces the topological finiteness condition finite derivation type   (FDT) on the class of semigroups. This notion is naturally extended from the monoid case. With this new concept we are able to prove that if a Rees matrix semigroup M[S;I,J;P]$M[S;I,J;P]$ has FDT then the semigroup S$S$ also has FDT. Given a monoid S$S$ and a finitely presented Rees matrix semigroup M[S;I,J;P]$M[S;I,J;P]$ we prove that if the ideal of S$S$ generated by the entries of P$P$ has FDT, then so does M[S;I,J;P]$M[S;I,J;P]$. In particular, we show that, for a finitely presented completely simple semigroup M$M$, the Rees matrix semigroup M=M[S;I,J;P]$M=M[S;I,J;P]$ has FDT if and only if the group S$S$ has FDT.     

Extended dominance and a stochastic shortest path problem

In the context of stochastic networks, we study the problem of finding a path P   that combines in a reasonable way the mean m(P)$m(P)$ and variance v(P)$v(P)$ of its length. Specifically we study a separable objective function that combines these two path measures: namely, z(P)=f(m(P))+g(v(P))$z(P)=f(m(P))+g(v(P))$, where f$f$ is an increasing convex function and g is an increasing concave function. A new type of dominance (e-dominance), stronger than the standard form of dominance, is then introduced, and it is shown to satisfy a certain form of Bellman's optimality principle. This means that it is possible to modify existing label-setting and label-correcting methods by using e-dominance, and without sacrificing optimality. Computational experience with these enhanced labeling algorithms has been promising. Test results for a variety of sample problems show that the e-dominance criterion can often significantly reduce the number of nondominated path vectors, compared to the standard dominance criterion. We observe a consequent reduction in both computation time and storage requirements.     

HELAC-Onia: An automatic matrix element generator for heavy quarkonium physics

By the virtues of the Dyson–Schwinger equations, we upgrade the published code HELAC to be capable to calculate the heavy quarkonium helicity amplitudes in the framework of NRQCD factorization, which we dub HELAC-Onia. We rewrote the original HELAC to make the new program be able to calculate helicity amplitudes of multi P$P$-wave quarkonium states production at hadron colliders and electron–positron colliders by including new P$P$-wave off-shell currents. Therefore, besides the high efficiencies in computation of multi-leg processes within the Standard Model, HELAC-Onia is also sufficiently numerical stable in dealing with P$P$-wave quarkonia (e.g. _hc,b,_χc,b$h_{c,b},{\chi }_{c,b}$) and P$P$-wave color-octet intermediate states. To the best of our knowledge, it is a first general-purpose automatic quarkonium matrix elements generator based on recursion relations on the market.     

OptQC: An optimized parallel quantum compiler

The software package Qcompiler (Chen and Wang 2013) provides a general quantum compilation framework, which maps any given unitary operation into a quantum circuit consisting of a sequential set of elementary quantum gates. In this paper, we present an extended software OptQC  , which finds permutation matrices P$P$ and Q$Q$ for a given unitary matrix U$U$ such that the number of gates in the quantum circuit of U=Q^TP^TU^′PQ$U=Q^T{P}^T{U}^{\prime }PQ$ is significantly reduced, where U^′$U^{\prime }$ is equivalent to U$U$ up to a permutation and the quantum circuit implementation of each matrix component is considered separately. We extend further this software package to make use of high-performance computers with a multiprocessor architecture using MPI. We demonstrate its effectiveness in reducing the total number of quantum gates required for various unitary operators.     

On a compact encoding of the swap automaton

Given a string P of length m over an alphabet Σ of size σ, a swapped version of P is a string derived from P   by a series of local swaps, i.e., swaps of adjacent symbols, such that each symbol can participate in at most one swap. We present a theoretical analysis of the nondeterministic finite automaton for the language _?P′∈ΠPΣ^?P^′${?}_{P^{\prime }\in {\Pi }_P}{\Sigma }^{?}{P}^{\prime }$ (swap automaton, for short), where _ΠP${\Pi }_P$ is the set of swapped versions of P  . Our study is based on the bit-parallel simulation of the same automaton due to Fredriksson, and reveals an interesting combinatorial property that links the automaton to the one for the language Σ^?P${\Sigma }^{?}P$. By exploiting this property and the method presented by Cantone et al. (2012), we obtain a bit-parallel encoding of the swap automaton which takes O(σ²⌈k/w⌉)$O({\sigma }^2\lceil k/w\rceil )$ space and allows one to simulate the automaton on a string of length n   in time O(n⌈k/w⌉)$O(n\lceil k/w\rceil )$, where ⌈m/σ⌉?k?m$\lceil m/\sigma \rceil ?k?m$ is the size of a specific factorization of P defined by Cantone et al. (2012) and w is the word size in bits.     

On triangulation axes of polygons

We propose the triangulation axis as an alternative skeletal structure for a simple polygon P. This axis is a straight-line tree that can be interpreted as an anisotropic medial axis of P, where inscribed disks are line segments or triangles. The underlying triangulation that specifies the anisotropy can be varied, to adapt the axis so as to reflect predominant geometrical and topological features of P. Triangulation axes typically have much fewer edges and branchings than the Euclidean medial axis or the straight skeleton of P. Still, they retain important properties, as for example the reconstructability of P   from its skeleton. Triangulation axes can be computed from their defining triangulations in O(n)$O(n)$ time. We investigate the effect of using several optimal triangulations for P  . In particular, careful edge flipping in the constrained Delaunay triangulation leads, in O(nlog?n)$O(n\log ?n)$ overall time, to an axis competitive to ‘high quality axes’ requiring Θ(n³)$\Theta (n^3)$ time for optimization via dynamic programming.     

An efficient delay-optimal distributed termination detection algorithm

Distributed termination detection is a fundamental problem in parallel and distributed computing and numerous schemes with different performance characteristics have been proposed. These schemes, while being efficient with regard to one performance metric, prove to be inefficient in terms of other metrics. A significant drawback shared by all previous methods is that, on most popular topologies, they take Ω(P)$\mathrm{\Omega }(P)$ time to detect and signal termination after its actual occurrence, where P   is the total number of processing elements. Detection delay is arguably the most important metric to optimize, since it is directly related to the amount of idling of computing resources and to the delay in the utilization of results of the underlying computation. In this paper, we present a novel termination detection algorithm that is simultaneously optimal or near-optimal with respect to all relevant performance measures on any topology. In particular, our algorithm has a best-case detection delay of Θ(1)$\mathrm{\Theta }(1)$ and a finite optimal worst-case detection delay on any topology equal in order terms to the time for an optimal one-to-all broadcast on that topology (which we accurately characterize for an arbitrary topology). On k-ary n  -cube tori and meshes, the worst-case delay is Θ(D)$\mathrm{\Theta }(D)$, where D   is the diameter of the target topology. Further, our algorithm has message and computational complexities of Θ(MD+P)$\mathrm{\Theta }(\mathit{MD}+P)$ in the worst case and, for most applications, Θ(M+P)$\mathrm{\Theta }(M+P)$ in the average case—the same as other message-efficient algorithms, and an optimal space complexity of Θ(P)$\mathrm{\Theta }(P)$, where M is the total number of messages used by the underlying computation. We also give a scheme using counters that greatly reduces the constant associated with the average message and computational complexities, but does not suffer from the counter-overflow problems of other schemes. Finally, unlike some previous schemes, our algorithm does not rely on first-in first-out (FIFO) ordering for message communication to work correctly.     

On the robust control of stable minimum phase plants with large uncertainty in a time constant. A fractional-order control approach

This paper addresses the problem of designing controllers that are robust to a great uncertainty in a time constant of the plant. Plants must be represented by minimum phase rational transfer functions of an arbitrary order. The design specifications are: (1) a phase margin for the nominal plant, (2) a gain crossover frequency for the nominal plant, (3) zero steady state error to step commands, and (4) a constant phase margin for all the possible values of the time constant (T$T$): 0<T<∞$0<T<\infty$. We propose a theorem that defines the structure of the set of controllers that fulfil these specifications and show that it is necessary for these robust controllers to include a fractional-order PI$PI$ term. Examples are developed for both stable and unstable plants, and the results are compared with a standard PI$PI$ controller and a robust controller designed using the QFT$QFT$ methodology.     

An iterative algorithm for solving a pair of matrix equations over generalized centro-symmetric matrices

A matrix is said to be a symmetric orthogonal matrix if . A matrix is said to be generalized centro-symmetric (generalized central anti-symmetric) with respect to P, if A=PAP (A=−PAP). The generalized centro-symmetric matrices have wide applications in information theory, linear estimate theory and numerical analysis. In this paper, we propose a new iterative algorithm to compute a generalized centro-symmetric solution of the linear matrix equations . We show, when the matrix equations are consistent over generalized centro-symmetric matrix Y, for any initial generalized centro-symmetric matrix Y₁, the sequence {Y_k} generated by the introduced algorithm converges to a generalized centro-symmetric solution of matrix equations . The least Frobenius norm generalized centro-symmetric solution can be derived when a special initial generalized centro-symmetric matrix is chosen. Furthermore, the optimal approximation generalized centro-symmetric solution to a given generalized centro-symmetric matrix can be derived. Several numerical examples are given to show the efficiency of the presented method.