Stratification associated with local b-functions

The local b$b$-function _bf,p(s)$b_{f,p}\left(s\right)$ of an n$n$-variate polynomial f∈C[x]$f\in \mathbb{C}\left[x\right]$ (x=(_x1,…,_xn)$x=(x_1,\dots ,x_n)$) at a point p∈Cⁿ$p\in {\mathbb{C}}^n$ is constant on each stratum of a stratification of Cⁿ${\mathbb{C}}^n$. We propose a new method for computing such a stratification and _bf,p(s)$b_{f,p}\left(s\right)$ on each stratum. In the existing method proposed in Oaku (1997b), a primary ideal decomposition of an ideal in C[x,s]$\mathbb{C}[x,s]$ is needed and our experiment shows that the primary decomposition can be a bottleneck for computing the stratification. In our new method, the computation can be done by just computing ideal quotients and examining inclusions of algebraic sets. The precise form of a stratum can be obtained by computing the decomposition of the radicals of the ideals in C[x]$\mathbb{C}\left[x\right]$ defining the stratum. We also introduce various techniques for improving the practical efficiency of the implementation and we show results of computations for some examples.     

Multicriteria 0-1 knapsack problems with k-min objectives

This paper deals with the multicriteria 0-1 knapsack problem (KP) with k$k$-min objectives (MkMIN-KP) in which the first objective is of classical sum type and the remaining objectives are k$k$-min objective functions. The k$k$-min objectives are ordinal objectives, aiming at the maximization of the k$k$ th smallest objective coefficient in any feasible knapsack solution with at least k$k$ items in the knapsack. We develop efficient algorithms for the determination of the complete nondominated set of MkMIN-KP.     

An approximation algorithm to the k-Steiner Forest problem

Given a graph G$G$, an integer k$k$, and a demand set D={(_s1,_t1),…,(_sl,_tl)}$D=\{(s_1,t_1),\dots ,(s_l,t_l)\}$, the k$k$-Steiner Forest problem finds a forest in graph G$G$ to connect at least k$k$ demands in D$D$ such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n^2/3logl)$O(n^{2/3}logl)$. We give a simpler and faster approximation algorithm to this problem with performance ratio O(n^2/3logk)$O(n^{2/3}logk)$ via greedy approach, improving the previously best known ratio in the literature.     

Set-theoretic generators of rational space curves

We show how to calculate three low degree set-theoretic generators (i.e., algebraic surfaces) for all rational space curves of low degree (degree ≤6$\le 6$) as well as for all higher degree rational space curves where at least one element of their μ$\mu$-basis has degree 1 from a μ$\mu$-basis of the parametrization. In addition to having low degree, at least two of these surface generators are always ruled surfaces. Whenever possible we also show how to compute two set-theoretic complete intersection generators for these rational space curves from a μ$\mu$-basis of their parametrization.     

Algorithms for a class of infinite permutation groups

Motivated by the famous 3n+1$3n+1$ conjecture, we call a mapping from Z$\mathbb{Z}$ to Z$\mathbb{Z}$residue-class-wise affine   if there is a positive integer m$m$ such that it is affine on residue classes (mod m$m$). This article describes a collection of algorithms and methods for computation in permutation groups and monoids formed by residue-class-wise affine mappings.     

Simplifying the weft hierarchy

We give simple, self-contained proofs of the basic hardness results for the classes W[t]$W[t]$ of the weft hierarchy. We extend these proofs to higher levels of the hierarchy and illuminate the distinctions among its classes. The anti-monotone collapse at W[1,s]$W[1,s]$ and the normalization of weft-t$t$ formulas arise as by-products of the proofs.     

Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes

In this paper, we investigate the fault-tolerant capabilities of the k-ary n-cubes for even integer k with respect to the hamiltonian and hamiltonian-connected properties. The k-ary n-cube is a bipartite graph if and only if k is an even integer. Let F   be a faulty set with nodes and/or links, and let k?3$k?3$ be an odd integer. When |F|?2n-2$\left|F\right|?2n-2$, we show that there exists a hamiltonian cycle in a wounded k-ary n  -cube. In addition, when |F|?2n-3$\left|F\right|?2n-3$, we prove that, for two arbitrary nodes, there exists a hamiltonian path connecting these two nodes in a wounded k-ary n-cube. Since the k-ary n  -cube is regular of degree 2n$2n$, the degrees of fault-tolerance 2n-3$2n-3$ and 2n-2$2n-2$ respectively, are optimal in the worst case.     

A new variance-based global sensitivity analysis technique

A new set of variance-based sensitivity indices, called W$W$-indices, is proposed. Similar to the Sobol’s indices, both main and total effect indices are defined. The W$W$-main effect indices measure the average reduction of model output variance when the ranges of a set of inputs are reduced, and the total effect indices quantify the average residual variance when the ranges of the remaining inputs are reduced. Geometrical interpretations show that the W$W$-indices gather the full information of the variance ratio function, whereas, Sobol’s indices only reflect the marginal information. Then the double-loop-repeated-set Monte Carlo (MC) (denoted as DLRS MC) procedure, the double-loop-single-set MC (denoted as DLSS MC) procedure and the model emulation procedure are introduced for estimating the W$W$-indices. It is shown that the DLRS MC procedure is suitable for computing all the W$W$-indices despite its highly computational cost. The DLSS MC procedure is computationally efficient, however, it is only applicable for computing low order indices. The model emulation is able to estimate all the W$W$-indices with low computational cost as long as the model behavior is correctly captured by the emulator. The Ishigami function, a modified Sobol’s function and two engineering models are utilized for comparing the W$W$- and Sobol’s indices and verifying the efficiency and convergence of the three numerical methods. Results show that, for even an additive model, the W$W$-total effect index of one input may be significantly larger than its W$W$-main effect index. This indicates that there may exist interaction effects among the inputs of an additive model when their distribution ranges are reduced.     

Thread vulnerability in parallel applications

Continuously reducing transistor sizes and aggressive low power operating modes employed by modern architectures tend to increase transient error rates. Concurrently, multicore machines are dominating the architectural spectrum today in various application domains. These two trends require a fresh look at resiliency of multithreaded applications against transient errors from a software perspective. In this paper, we propose and evaluate a new metric called the Thread Vulnerability Factor (TVF$TVF$). A distinguishing characteristic of TVF$TVF$ is that its calculation for a given thread (which is typically one of the threads of a multithreaded application) does not depend on its code alone, but also on the codes of the threads that share resources and data with that thread. As a result, we decompose TVF$TVF$ of a thread into two complementary parts: local and remote. While the former captures the TVF$TVF$ induced by the code of the target thread, the latter represents the vulnerability impact of the threads that interact with the target thread. We quantify the local and remote TVF$TVF$ values for three architectural components (register file, ALUs, and caches) using a set of ten multithreaded applications from the Parsec and Splash-2 benchmark suites. Our experimental evaluation shows that TVF$TVF$ values tend to increase as the number of cores increases, which means the system becomes more vulnerable as the core count rises. We further discuss how TVF$TVF$ metric can be employed to explore performance–reliability tradeoffs in multicores. Reliability-based analysis of compiler optimizations and redundancy-based fault tolerance are also mentioned as potential usages of our TVF$TVF$ metric.     

Separation of synchronous and asynchronous communication via testing

One of the early results concerning the asynchronous π$\pi$-calculus which significantly contributed to its popularity is the capability of encoding the output prefix of the (choiceless) π$\pi$-calculus in a natural and elegant way. Encodings of this kind were proposed by Honda and Tokoro, by Nestmann and (independently) by Boudol. We investigate whether the above encodings preserve De Nicola and Hennessy’s testing semantics. In this sense, it turns out that, under some general conditions, no encoding of the output prefix is able to preserve the must testing. This negative result is due to (a) the non-atomicity of the sequences of steps which are necessary in the asynchronous π$\pi$-calculus to mimic synchronous communication, and (b) testing semantics’ sensitivity to divergence.     

Are Buchberger’s criteria necessary for the chain condition?

Buchberger’s Gröbner basis theory plays a fundamental role in symbolic computation. The resulting algorithms essentially carry out several S$S$-polynomial reductions. In his Ph.D. thesis and later publication Buchberger showed that sometimes one can skip S$S$-polynomial reductions if the leading terms of polynomials satisfy certain criteria. A question naturally arises: Are Buchberger’s criteria also necessary   for skipping S$S$-polynomial reductions? In this paper, after making the question more precise (in terms of a chain condition), we show the answer to be “almost, but not quite”: necessary when there are four or more polynomials, but not necessary when there are exactly three polynomials. For that case, we found an extension to Buchberger’s criteria that is necessary as well as sufficient.     

Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices

K$K$-way hypergraph partitioning has an ever-growing use in parallelization of scientific computing applications. We claim that hypergraph partitioning with multiple constraints and fixed vertices should be implemented using direct K$K$-way refinement, instead of the widely adopted recursive bisection paradigm. Our arguments are based on the fact that recursive-bisection-based partitioning algorithms perform considerably worse when used in the multiple constraint and fixed vertex formulations. We discuss possible reasons for this performance degradation. We describe a careful implementation of a multi-level direct K$K$-way hypergraph partitioning algorithm, which performs better than a well-known recursive-bisection-based partitioning algorithm in hypergraph partitioning with multiple constraints and fixed vertices. We also experimentally show that the proposed algorithm is effective in standard hypergraph partitioning.     

A CPS encoding of name-passing in Higher-order mobile embedded resources

We present an encoding of the synchronous π$\pi$-calculus in the calculus of Higher-order mobile embedded resources (Homer), a pure higher-order calculus with mobile processes in nested locations, defined as a simple, conservative extension of the core process-passing subset of Thomsen's Plain CHOCS. We prove that our encoding is fully abstract with respect to barbed bisimulation and sound with respect to barbed congruence. Our encoding demonstrates that higher-order process-passing together with mobile resources in, possibly local, named locations are sufficient to express π$\pi$-calculus name-passing. The encoding uses a novel continuation passing style to facilitate the encoding of synchronous communication.     

Accelerating knowledge-based energy evaluation in protein structure modeling with Graphics Processing Units

Evaluating the energy of a protein molecule is one of the most computationally costly operations in many protein structure modeling applications. In this paper, we present an efficient implementation of knowledge-based energy functions by taking advantage of the recent Graphics Processing Unit (GPU) architectures. We use DFIRE, a knowledge-based all-atom potential, as an example to demonstrate our GPU implementations on the latest NVIDIA Fermi architecture. A load balancing workload distribution scheme is designed to assign computations of pair-wise atom interactions to threads to achieve perfect or near-perfect load balancing in the symmetric N$N$-body problem in DFIRE. Reorganizing atoms in the protein also improves the cache efficiency in Fermi GPU architecture, which is particularly effective for small proteins. Our DFIRE implementation on GPU (GPU-DFIRE) has exhibited a speedup of up to ∼$\sim$150 on NVIDIA Quadro FX3800M and ∼$\sim$250 on NVIDIA Tesla M2050 compared to the serial DFIRE implementation on CPU. Furthermore, we show that protein structure modeling applications, including a Monte Carlo sampling program and a local optimization program, can benefit from GPU-DFIRE with little programming modification but significant computational performance improvement.     

Open bisimulation,revisited

In the context of the π$\pi$-calculus, open bisimulation is prominent and popular due to its congruence properties and its easy implementability. Motivated by the attempt to generalise it to the spi-calculus, we offer a new, more refined definition and show how far it coincides with the original one.     

Non-associative Gröbner bases,finitely-presented Lie rings and the Engel condition,II

We give an algorithm for constructing a basis and a multiplication table of a finite-dimensional finitely-presented Lie ring. Secondly, we give relations that are equivalent to the n$n$-Engel condition, and only have to be checked for the elements of a basis of a Lie ring. We apply this to construct the freest t$t$-generator Lie rings that satisfy the n$n$-Engel condition, for (t,n)=(2,3),(3,3),(4,3),(2,4)$(t,n)=(2,3),(3,3),(4,3),(2,4)$.     

Tag systems and Collatz-like functions

Tag systems were invented by Emil Leon Post and proven recursively unsolvable by Marvin Minsky. These production systems have proved to be very useful in constructing small universal (Turing complete) systems for several different classes of computational systems, including Turing machines, and are thus important instruments for studying limits or boundaries of solvability and unsolvability. Although there are some results on tag systems and their limits of solvability and unsolvability, there are hardly any that consider both   the shift number v$v$ and the number of symbols μ$\mu$. This paper aims to contribute to research on limits of solvability and unsolvability for tag systems, taking into account these two parameters. The main result is the reduction of the 3n+1$3n+1$-problem to a surprisingly small tag system. It indicates that the present unsolvability line–defined in terms of μ$\mu$ and v$v$–for tag systems might be significantly decreased.     

Optimal coverage of an infrastructure network using sensors with distance-decaying sensing quality

Motivated by recent applications of wireless sensor networks in monitoring infrastructure networks, we address the problem of optimal coverage of infrastructure networks using sensors whose sensing performance decays with distance. We show that this problem can be formulated as a continuous p-median problem on networks. The literature has addressed the discrete p-median problem   on networks and in continuum domains, and the continuous p$p$-median problem in continuum domains extensively. However, in-depth analysis of the continuous p$p$-median problem on networks has been lacking. With the sensing performance model that decays with distance, each sensor covers a region equivalent to its Voronoi partition on the network in terms of the shortest path distance metric. Using Voronoi partitions, we define a directional partial derivative of the coverage metric with respect to a sensor’s location. We then propose a gradient descent algorithm to obtain a locally optimal solution with guaranteed convergence. The quality of an optimal solution depends on the choice of the initial configuration of sensors. We obtain an initial configuration using two approaches: by solving the discrete p$p$-median problem on a lumped   network and by random sampling. We consider two methods of random sampling: uniform sampling and D²$D^2$-sampling. The first approach with the initial solution of the discrete p$p$-median problem leads to the best coverage performance for large networks, but at the cost of high running time. We also observe that the gradient descent on the initial solution with the D²$D^2$-sampling method yields a solution that is within at most 7% of the previous solution and with much shorter running time.