Irregular Primes and Cyclotomic Invariants to 12 Million

Computations of irregular primes and associated cyclotomic invariants were extended to all primes up to 12 million using multisectioning/convolution methods and a novel approach which originated in the study of Stickelberger codes Shokrollahi (1996). The latter idea reduces the problem to that of finding zeros of a polynomial overF_pof degree  <  (p −  1) / 2 among the quadratic nonresidues mod p. Use of fast polynomial gcd-algorithms gives anO (p log²p loglog p)-algorithm for this task. A more efficient algorithm, with comparable asymptotic running time, can be obtained by using Schönhage–Strassen integer multiplication techniques and fast multiple polynomial evaluation algorithms; this approach is particularly efficient when run on primes p for whichp −  1 has small prime factors. We also give some improvements on previous implementations for verifying the Kummer–Vandiver conjecture and for computing the cyclotomic invariants of a prime.     

Tyrolean termination tool: Techniques and features

The Tyrolean Termination Tool (T_TT for short) is a powerful tool for automatically proving termination of rewrite systems. It incorporates several new refinements of the dependency pair method that are easy to implement, increase the power of the method, result in simpler termination proofs, and make the method more efficient. T_TT employs polynomial interpretations with negative coefficients, like x − 1 for a unary function symbol or x − y for a binary function symbol, which are useful for extending the class of rewrite systems that can be proved terminating automatically. Besides a detailed account of these techniques, we describe the convenient web interface of T_TT and provide some implementation details.     

Scalable 2D Convex Hull and Triangulation Algorithms for Coarse Grained Multicomputers

In this paper we describe scalable parallel algorithms for building the convex hull and a triangulation ofncoplanar points. These algorithms are designed for thecoarse grained multicomputermodel:pprocessors withO(n/p)⪢O(1) local memory each, connected to some arbitrary interconnection network. They scale over a large range of values ofnandp, assuming only thatn⩾p^1+ε(ε>0) and require timeO((T_sequential/p)+T_s(n, p)), whereT_s(n, p) refers to the time of a global sort ofndata on approcessor machine. Furthermore, they involve only a constant number of global communication rounds. Since computing either 2D convex hull or triangulation requires timeT_sequential=Θ(n log n) these algorithms either run in optimal time,Θ((n log n)/p), or in sort time,T_s(n, p), for the interconnection network in question. These results become optimal whenT_sequential/pdominatesT_s(n, p) or for interconnection networks like the mesh for which optimal sorting algorithms exist.     

Transition-aware DVS algorithm for real-time systems using tree structure analysis

Dynamic voltage scaling (DVS) is a key technique for embedded real-time systems to reduce energy consumption by lowering the supply voltage and operating frequency. Many existing DVS algorithms have to generate the canonical schedules or estimate the lengths of slack time in advance for generating the voltage scaling decisions. Therefore, these methods have to compute the schedules with exponential time complexities in general. In this paper, we consider a set of jitter-controlled, independent, periodic, hard real-time tasks scheduled according to preemptive pinwheel model. Our approach constructs a tree structure corresponding to a schedule and maintains the data structure at each early-completion point. Our approach consists of off-line and on-line algorithms which consider the effects of transition time and energy. The off-line and on-line algorithm takes O(k + n log n) and O(k + (p_max/p_min)) time complexity, respectively, where n, k, p_max and p_min denotes the number of tasks, jobs, longest and shortest task period, respectively. Experimental results show that the proposed approach is effective in reducing computational complexity, transition time and energy overhead.     

Evaluation of response characteristics of resistive oxygen sensors based on porous cerium oxide thick film using pressure modulation method

In order to reduce the response time of resistive oxygen sensors using porous cerium oxide thick film, it is important to ascertain the factors controlling response. Pressure modulation method (PMM) was used to find the rate-limiting step of sensor response. This useful method measures the amplitude of sensor output (H(f)) for the sine wave modulation of oxygen partial pressure at constant frequency (f). In PMM, “break” response time, which is minimum period in which the sensor responds precisely, can be measured. Three points were examined: (1) simulated calculations of PMM were carried out using a model of porous thick film in which spherical particles are connected in a three-dimensional network; (2) sensor response speed was experimentally measured using PMM; and (3) the diffusion coefficient and surface reaction coefficient were estimated by comparison between experiment and calculation. The plot of log f versus log H(f) in the high f region was found to have a slope of approximately −0.5 for both porous thick film and non-porous thin film, when the rate-limiting step was diffusion. Calculations showed the response time of porous thick film was 1/20 that of non-porous thin film when the grain diameter of the porous thick film was the same as the thickness of non-porous thin film. At 973 K, “break” response time (t_b) of the resistive oxygen sensor was found by experiment to be 109 ms. It was concluded that the response of the resistive oxygen sensor prepared in this study was strongly controlled by diffusion at 923–1023 K, since the experiment revealed that the slope of plot of log f versus log H(f) in the high f region was approximately −0.5. At 923–1023 K, the diffusion coefficient of oxygen vacancy in porous ceria (D_V) was expressed as follows: D_V (m²s⁻¹) = 5.78 × 10⁻⁴ exp(−1.94 eV/kT). At 1023 K, the surface reaction coefficient (K) was found to exceed 10⁻⁴ m/s.     

Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data

In this paper, we consider an ordinal on-line scheduling problem. A sequence of n independent jobs has to be assigned non-preemptively to two uniformly related machines. We study two objectives which are maximizing the minimum machine completion time, and minimizing the l_p norm of the completion times. It is assumed that the values of the processing times of jobs are unknown at the time of assignment. However it is known in advance that the processing times of arriving jobs are sorted in a non-increasing order. We are asked to construct an assignment of all jobs to the machines at time zero, by utilizing only ordinal data rather than actual magnitudes of jobs. For the problem of maximizing the minimum completion time we first present a comprehensive lower bound on the competitive ratio, which is a piecewise function of machine speed ratio s. Then, we propose an algorithm which is optimal for any s ⩾ 1. For minimizing the l_p norm, we study the case of identical machines (s = 1) and present tight bounds as a function of p.     

Randomized control of T-policy for an M/G/1 system

We study an M/G/1 queueing system with a server that can be switched on and off. The server can take a vacation time T after the system becomes empty. In this paper, we investigate a randomized policy to control a server with which, when the system is empty, the server can be switched off with probability p and take a vacation or left on with probability (1 − p) and continue to serve the arriving customers. For this system, we consider the operating cost and the holding cost where the operating cost consists of the system running and switching costs (start up and shut down costs). We describe the structure and characteristics of this policy and solve a constrained problem to minimize the average operating cost per unit time under the constraint for the holding cost per unit time.     

GPU-based parallel vertex substitution algorithm for the p-median problem

We introduce a GPU-based parallel vertex substitution (pVS) algorithm for the p-median problem using the CUDA architecture by NVIDIA. pVS is developed based on the best profit search algorithm, an implementation of vertex substitution (VS), that is shown to produce reliable solutions for p-median problems. In our approach, each candidate solution in the entire search space is allocated to a separate thread, rather than dividing the search space into parallel subsets. This strategy maximizes the usage of GPU parallel architecture and results in a significant speedup and robust solution quality. Computationally, pVS reduces the worst case complexity from sequential VS’s O(p · n²) to O(p · (n ? p)) on each thread by parallelizing computational tasks on GPU implementation. We tested the performance of pVS on two sets of numerous test cases (including 40 network instances from OR-lib) and compared the results against a CPU-based sequential VS implementation. Our results show that pVS achieved a speed gain ranging from 10 to 57 times over the traditional VS in all test network instances.     

Electrochemical determination of ascorbic acid in fruits on a vanadium oxide polypropylene carbonate modified electrode

A novel vanadium oxide polypropylene carbonate modified glassy carbon electrode was developed and used for the measurement of ascorbic acid (AA). The electrode was prepared by casting a mixture of vanadium tri(isopropoxide) oxide (VO(OC₃H₇)₃) and poly(propylene carbonate) (PPC) onto the surface of a glassy carbon electrode. The electrochemical behavior of the VO(OC₃H₇)₃–PPC film modified glassy carbon electrode was investigated by cyclic voltammetry and amperometry. This modified electrode exhibited electrocatalytic response to the oxidation of ascorbic acid. Compared with a bare glassy carbon electrode, the modified electrode exhibits a 220 mV shift of the oxidation potential of ascorbic acid in the cathodic direction and a marked enhancement of the current response. The response current revealed a good linear relationship with the concentration of ascorbic acid in the range of 4 × 10⁻⁸ and 1 × 10⁻⁴ mol L⁻¹ and the detection limit of 1.5 × 10⁻⁸ mol L⁻¹ (S/N = 3) in the pH 8.06 Britton–Robinson solution. Quantitative recovery of the ascorbic acid in synthetic samples has been obtained and the interferences from different species have been studied. The method has been successfully applied to the determination of ascorbic acid in fruits. The concentrations of ascorbic acid measured by this method are in good agreement with the literature value. It is much promising for the modified films to be used as an electrochemical sensor for the detection of ascorbic acid.     

Hybrid real-coded genetic algorithm for data partitioning in multi-round load distribution and scheduling in heterogeneous systems

Data partitioning and scheduling is one the important issues in minimizing the processing time for parallel and distributed computing system. We consider a single-level tree architecture of the system and the case of affine communication model, for a general m processor system with n rounds of load distribution. For this case, there exists an optimal activation order, optimal number of processors m* (m * ≤ m), and optimal rounds of load distribution n* (n * ≤ n), such that the processing time of the entire processing load is a minimum. This is a difficult optimization problem because for a given activation order, we have to first identify the processors that are participating (in the computation process) in every round of load distribution and then obtain the load fractions assigned to them, and the processing time. Hence, in this paper, we propose a real-coded genetic algorithm (RCGA) to solve the optimal activation order, optimal number of processors m* (m * ≤ m), and optimal rounds of load distribution n* (n * ≤ n), such that the processing time of the entire processing load is a minimum. RCGA employs a modified crossover and mutation operators such that the operators always produce a valid solution. Also, we propose different population initialization schemes to improve the convergence. Finally, we present a comparative study with simple real-coded genetic algorithm and particle swarm optimization to highlight the advantage of the proposed algorithm. The results clearly indicate the effectiveness of the proposed real-coded genetic algorithm.     

Coarse-Grained Parallel Geometric Search

We present a parallel algorithm for solving thenext element search problemon a set of line segments, using a BSP-like model referred to as thecoarse grained multicomputer(CGM). The algorithm requiresO(1) communication rounds (h-relations withh=O(n/p)),O((n/p) log n) local computation, andO((n/p) log p) memory per processor, assumingn/p⩾p. Our result implies solutions to the point location, trapezoidal decomposition, and polygon triangulation problems. A simplified version for axis-parallel segments requires onlyO(n/p) memory per processor, and we discuss an implementation of this version. As in a previous paper by Develliers and Fabri (Int. J. Comput. Geom. Appl.6(1996), 487–506), our algorithm is based on a distributed implementation of segment trees which are of sizeO(n log n). This paper improves onop. cit.in several ways: (1) It studies the more general next element search problem which also solves, e.g., planar point location. (2) The algorithms require onlyO((n/p) log n) local computation instead ofO(log p*(n/p) log n). (3) The algorithms require onlyO((n/p) log p) local memory instead ofO((n/p) log n).     

Remote sensing of canopy light use efficiency in temperate and boreal forests of North America using MODIS imagery

Light use efficiency (LUE) is an important variable characterizing plant eco-physiological functions and refers to the efficiency at which absorbed solar radiation is converted into photosynthates. The estimation of LUE at regional to global scales would be a significant advantage for global carbon cycle research. Traditional methods for canopy level LUE determination require meteorological inputs which cannot be easily obtained by remote sensing. Here we propose a new algorithm that incorporates the enhanced vegetation index (EVI) and a modified form of land surface temperature (T_m) for the estimation of monthly forest LUE based on Moderate Resolution Imaging Spectroradiometer (MODIS) imagery. Results demonstrate that a model based on EVI × T_m parameterized from ten forest sites can provide reasonable estimates of monthly LUE for temperate and boreal forest ecosystems in North America with an R² of 0.51 (p < 0.001) for the overall dataset. The regression coefficients (a, b) of the LUE–EVI × T_m correlation for these ten sites have been found to be closely correlated with the average EVI (EVI_ave, R² = 0.68, p = 0.003) and the minimum land surface temperature (LST_min, R² = 0.81, p = 0.009), providing a possible approach for model calibration. The calibrated model shows comparably good estimates of LUE for another ten independent forest ecosystems with an overall root mean square error (RMSE) of 0.055 g C per mol photosynthetically active radiation. These results are especially important for the evergreen species due to their limited variability in canopy greenness. The usefulness of this new LUE algorithm is further validated for the estimation of gross primary production (GPP) at these sites with an RMSE of 37.6 g C m^? 2 month^? 1 for all observations, which reflects a 28% improvement over the standard MODIS GPP products. These analyses should be helpful in the further development of ecosystem remote sensing methods and improving our understanding of the responses of various ecosystems to climate change.     

Bounds for the Roots of Lacunary Polynomials

A polynomial P(X)  = X^d + a_d − 1X^d − 1 + ⋯ is called lacunary when a_d − 1 =  0. We give bounds for the roots of such polynomials with complex coefficients. These bounds are much smaller than for general polynomials.     

Highly fault-tolerant cycle embeddings of hypercubes

The hypercube Q_n is one of the most popular networks. In this paper, we first prove that the n-dimensional hypercube is 2n − 5 conditional fault-bipancyclic. That is, an injured hypercube with up to 2n − 5 faulty links has a cycle of length l for every even 4 ⩽ l ⩽ 2ⁿ when each node of the hypercube is incident with at least two healthy links. In addition, if a certain node is incident with less than two healthy links, we show that an injured hypercube contains cycles of all even lengths except hamiltonian cycles with up to 2n − 3 faulty links. Furthermore, the above two results are optimal. In conclusion, we find cycles of all possible lengths in injured hypercubes with up to 2n − 5 faulty links under all possible fault distributions.     

On reliability of the folded hypercubes

In this paper, we explore the 2-extra connectivity and 2-extra-edge-connectivity of the folded hypercube FQ_n. We show that κ₂(FQ_n) = 3n − 2 for n ⩾ 8; and λ₂(FQ_n) = 3n − 1 for n ⩾ 5. That is, for n ⩾ 8 (resp. n ⩾ 5), at least 3n − 2 vertices (resp. 3n − 1 edges) of FQ_n are removed to get a disconnected graph that contains no isolated vertices (resp. edges). When the folded hypercube is used to model the topological structure of a large-scale parallel processing system, these results can provide more accurate measurements for reliability and fault tolerance of the system.     

Fast Constructive Recognition of a Black Box Group Isomorphic toSnorAnusing Goldbach’s Conjecture

The well-known Goldbach Conjecture (GC) states that any sufficiently large even number can be represented as a sum of two odd primes. Although not yet demonstrated, it has been checked for integers up to 10¹⁴. Using two stronger versions of the conjecture, we offer a simple and fast method for recognition of a gray box group G known to be isomorphic to S_n(or A_n) with knownn ≥  20, i.e. for construction1of an isomorphism from G toS_n (or A_n). Correctness and rigorous worst case complexity estimates rely heavily on the conjectures, and yield times of O([ρ + ν + μ ] n log²n) or O([ ρ + ν + μ ] n logn / loglog n) depending on which of the stronger versions of the GC is assumed to hold. Here,ρ is the complexity of generating a uniform random element of G, ν is the complexity of finding the order of a group element in G, and μ is the time necessary for group multiplication in G. Rigorous lower bound and probabilistic approach to the time complexity of the algorithm are discussed in the Appendix.     

Simulation of solid thermal explosion and liquid thermal explosion of dicumyl peroxide using calorimetric technique

Dicumyl peroxide (DCPO), is produced by cumene hydroperoxide (CHP) process, is utilized as an initiator for polymerization, a prevailing source of free radicals, a hardener, and a linking agent. DCPO has caused several thermal explosion and runaway reaction accidents in reaction and storage zone in Taiwan because of its unstable reactive property. Differential scanning calorimetry (DSC) was used to determine thermokinetic parameters including 700 J g^–1 of heat of decomposition (ΔH_d), 110 °C of exothermic onset temperature (T₀), 130 kJ mol^–1 of activation energy (E_a), etc., and to analyze the runaway behavior of DCPO in a reaction and storage zone. To evaluate thermal explosion of DCPO with storage equipment, solid thermal explosion (STE) and liquid thermal explosion (LTE) of thermal safety software (TSS) were applied to simulate storage tank under various environmental temperatures (T_e). T_e exceeding the T₀ of DCPO can be discovered as a liquid thermal explosion situation. DCPO was stored under room temperature without sunshine and was prohibited exceeding 67 °C of self-accelerating decomposition temperature (SADT) for a tank (radius = 1 m and height = 2 m). SADT of DCPO in a box (width, length and height = 1 m, respectively) was determined to be 60 °C. The TSS was employed to simulate the fundamental thermal explosion behavior in a large tank or a drum. Results from curve fitting demonstrated that, even at the earlier stage of the reaction in the experiments, ambient temperature could elicit exothermic reactions of DCPO. To curtail the extent of the risk, relevant hazard information is quite significant and must be provided in the manufacturing process.     

The possibility of using C20 fullerene and graphene as semiconductor segments for detection,and destruction of cyanogen-chloride chemical agent

Detection of hazardous chemical species by changing the electrical conductivity of a semiconductor matter is a proposed and applied way for decreasing their subsequent unpleasant effects. Recently, many examples of using inorganic or organic materials, polymeric, and also nano-sized species as sensors were reported in which, in some cases, those matters were strongly affective and suitable.In this project, we have made an assessment on whether the graphene segment or C₂₀ fullerene, able to sense the existence of cyanogen chloride NCCl? In order to gain trustable results, the possible reaction pathways along with the adsorption kinetics were investigated. Moreover, the electronic density of states DOS showed that C₂₀ fullerene senses the existence of cyanogen chloride agent with a clearer signal (ΔE_g = 0.0110 eV) compared to the graphene segment (ΔE_g = 0.0001 eV). Also the adsorption energy calculations showed that cyanogen chloride could be adsorbed by the fullerene in a multi-step process (E_ads1 = −0.852 kcal mol⁻¹; E_ads2 = −0.446 kcal mol⁻¹; E_ads3 = −2.330 kcal mol⁻¹).     

Minimizing cost-related objective in synchronous scheduling of parallel factories in the virtual production network

This paper will introduce the Monte Carlo-based heuristic with seven local searches (LSs) which are carefully designed for distributed production network scheduling. Distributed production network consists of the number of different individual factories that joins together to form a network, in which these factories can operate more economically than operating individually and each individual factory usually focuses on self-benefits. Some realistic features such as heterogeny of factories and the transportation among factories are incorporated in our problem definition. However, in such network, each individual factory usually focuses on self-benefits and it plans to optimize its own profit. In this problem, among F exit factories in the network, F′ factories are interested in the total earliness costs and the remaining factories (F″ = F − F′) are interested in the total tardiness cost. Cost minimization is achieved through the minimization of earliness in F′factories, tardiness in F″ factories and the total costs of operation time of all jobs. This algorithm initializes with best known non-cooperative local scheduling and then the LSs search simultaneously through the same solution space, starting from the same current solution. Upon receiving the solutions from the LSs, the new solution will be accepted based on the Monte Carlo acceptance criterion. This criterion always accepts an improved solution and, in order to escape local minima, accept the worse solutions with a certain probability, which this probability decreases with deteriorating solutions. After solving the mixed integer linear programming by the CPLEX solver in the small-size instances, the results obtained by heuristic are compared with two genetic algorithms in the large-size instances. The results of the scheduling before cooperation in production network were also considered in the experiments.     

A fast fault-identification algorithm for bijective connection graphs using the PMC model

Diagnosis of reliability is an important topic for interconnection networks. Under the classical PMC model, Dahura and Masson [5] proposed a polynomial time algorithm with time complexity O(N^2.5) to identify all faulty nodes in an N-node network. This paper addresses the fault diagnosis of so called bijective connection (BC) graphs including hypercubes, twisted cubes, locally twisted cubes, crossed cubes, and Möbius cubes. Utilizing a helpful structure proposed by Hsu and Tan [20] that was called the extending star by Lin et al. [24], and noting the existence of a structured Hamiltonian path within any BC graph, we present a fast diagnostic algorithm to identify all faulty nodes in O(N) time, where N = 2ⁿ, n ? 4, stands for the total number of nodes in the n-dimensional BC graph. As a result, this algorithm is significantly superior to Dahura–Masson’s algorithm when applied to BC graphs.