Computing Local Artin Maps,and Solvability of Norm Equations

Let L = K(α) be an Abelian extension of degree n of a number field K, given by the minimal polynomial of α over K. We describe an algorithm for computing the local Artin map associated with the extension L / K at a finite or infinite prime v of K. We apply this algorithm to decide if a nonzero a ∈ K is a norm from L, assuming that L / K is cyclic.     

Integrating Factors for Second-order ODEs

A systematic algorithm for building integrating factors of the form μ(x, y), μ(x, y^′) or μ(y, y^′) for second-order ODEs is presented. The algorithm can determine the existence and explicit form of the integrating factors themselves without solving any differential equations, except for a linear ODE in one subcase of the μ (x, y) problem. Examples of ODEs not having point symmetries are shown to be solvable using this algorithm. The scheme was implemented in Maple, in the framework of the ODEtools package and its ODE-solver. A comparison between this implementation and other computer algebra ODE-solvers in tackling non-linear examples from Kamke's book is shown.     

Predicting guild commitment in World of Warcraft with the investment model of commitment

Many MMORPG offer players the possibility to become a member of a guild, a hierarchical organization of characters with common objectives. Guild membership can be beneficial to game progress, and offer opportunities for social interaction. In the current study we focus on the MMORPG World of Warcraft (WoW), with the main aim to examine whether guild commitment and players’ intention to remain in their guild can be predicted by players’ satisfaction, investments, and perceptions of alternatives to their guild. To this end, 165 WoW players completed an online questionnaire and answered questions related to their guild membership. They also completed the investment model scale which was reworded so all questions pertained to their guild and their fellow guild members. Results show that satisfaction level, quality of alternatives, and investment size significantly predict commitment level (p’s < .001), which in turn predicted likelihood of participants’ staying with their current guild (p < .001) and the number of guilds they had been a member of in the past (p < .001). Moreover, high levels of guild commitment were indicative of better mental health, whereas weekly hours of game play was negatively related to mental health. In the discussion, we conclude that interdependence theory and the investment model of commitment are applicable to online gaming environments, and we argue that commitment to one’s guild is one factor that could prevent the risks associated with online game play (i.e. problematic use).     

Composing Power Series Over a Finite Ring in Essentially Linear Time

Fix a finite commutative ringR. Letuandvbe power series overR, withv(0) = 0. This paper presents an algorithm that computes the firstnterms of the compositionu(v), given the firstnterms ofuandv, inn^1 + o(1)ring operations. The algorithm is very fast in practice whenRhas small characteristic.     

Gröbner Bases over Galois Rings with an Application to Decoding Alternant Codes

We develop a theory of Gröbner bases over Galois rings, following the usual formulation for Gröbner bases over finite fields. Our treatment includes a division algorithm, a characterization of Gröbner bases, and an extension of Buchberger’s algorithm. One application is towards the problem of decoding alternant codes over Galois rings. To this end we consider the module M =  {(a, b) :aS ≡ b  mod x^r} of all solutions to the so-called key equation for alternant codes, where S is a syndrome polynomial. In decoding, a particular solution (Σ, Ω)  ∈ M is sought satisfying certain conditions, and such a solution can be found in a Gröbner basis of M. Applying techniques introduced in the first part of this paper, we give an algorithm which returns the required solution.     

On the influence of the number of algorithms,problems, and independent runs in the comparison of evolutionary algorithms

When conducting a comparison between multiple algorithms on multiple optimisation problems it is expected that the number of algorithms, problems and even the number of independent runs will affect the final conclusions. Our question in this research was to what extent do these three factors affect the conclusions of standard Null Hypothesis Significance Testing (NHST) and the conclusions of our novel method for comparison and ranking the Chess Rating System for Evolutionary Algorithms (CRS4EAs). An extensive experiment was conducted and the results were gathered and saved of k = 16 algorithms on N = 40 optimisation problems over n = 100 runs. These results were then analysed in a way that shows how these three values affect the final results, how they affect ranking and which values provide unreliable results. The influence of the number of algorithms was examined for values k = {4, 8, 12, 16}, number of problems for values N = {5, 10, 20, 40}, and number of independent runs for values n = {10, 30, 50, 100}. We were also interested in the comparison between both methods – NHST's Friedman test with post-hoc Nemenyi test and CRS4EAs – to see if one of them has advantages over the other. Whilst the conclusions after analysing the values of k were pretty similar, this research showed that the wrong value of N can give unreliable results when analysing with the Friedman test. The Friedman test does not detect any or detects only a small number of significant differences for small values of N and the CRS4EAs does not have a problem with that. We have also shown that CRS4EAs is an appropriate method when only a small number of independent runs n are available.     

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.     

A distance-based aggregation approach for group decision making with interval preference orderings

Xu (2013) proposed a nonlinear programming model to derive an exact formula to determine the experts’ relative importance weights for the group decision making (GDM) with interval preference orderings. However, in this study, we show that the exact formula to determine the weight vector which always equals to w = (1/m, 1/m, … , 1/m)^T (m is the number of experts). In this paper, we propose a distance-based aggregation approach to assess the relative importance weights for GDM with interval preference orderings. Relevant theorems are offered to support the proposed approach. After that, by using the weighted arithmetic averaging operator, we obtain the aggregated virtual interval preference orderings. We propose a possibility degree formula to compare two virtual interval preference orderings, then rank and select the alternatives. The proposed method is tested by two numerical examples. Comparative analysis are provided to show the advantages and effectiveness of the proposed method.     

Algorithms for computing the maximum weight region decomposable into elementary shapes

Motivated by the image segmentation problem, we consider the following geometric optimization problem: Given a weighted n × n pixel grid, find the maximum weight region whose shape is decomposable into a set of disjoint elementary shapes. We give efficient algorithms for several interesting shapes. This is in strong contrast to finding the maximum weight region that is the union of elementary shapes for the corresponding cases—a problem that we prove to be NP-hard. We implemented one of the algorithms and demonstrate its applicability for image segmentation.     

High-speed and precise positioning of an X–Y table

Positioning plays an important role in manufacturing machines. This work presents a novel two-step controller strategy to achieve fast and precise positioning at the same time on an X–Y table that moves across the macro-dynamic range and settles to within the micro-dynamic resolution. The model dynamics in the macro- and the micro-region are both discussed and the controller design is separated into two parts to satisfy the requirements in each region. The switching condition of the controller is well defined. Experimental results indicate that the proposed two-step controller can move the system from the macro-region into the micro-region in 0.2 s with an accuracy of 1 μm.     

A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs

We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n^2ε+n^1−ε) log n) time, performing O(n^1+ε log n) work for any 0<ε<1/2. The strength of the algorithm is its simplicity, making it easy to implement and presumable quite efficient in practice. The algorithm improves upon the work of all previous parallel algorithms. Our algorithm is based on a region decomposition of the input graph and uses a well-known parallel implementation of Dijkstra's algorithm. The logarithmic factor in both the work and the time can be eliminated by plugging in a less practical, sequential planar shortest path algorithm together with an improved parallel implementation of Dijkstra's 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).     

Computer-based analysis of explicit approximations to the implicit Colebrook–White equation in turbulent flow friction factor calculation

The implicit Colebrook–White equation has been widely used to estimate the friction factor for turbulent fluid-flow in rough-pipes. In this paper, the state-of-the-art review for the most currently available explicit alternatives to the Colebrook–White equation, is presented. An extensive comparison test was established on the 20 × 500 grid, for a wide range of relative roughness (ε/D) and Reynolds number (R) values (1 × 10^?6 ? ε/D ? 5 × 10^?2; 4 × 10³ ? R ? 10⁸), covering a large portion of turbulent flow zone in Moody’s diagram. Based on the comprehensive error analysis, the magnitude points in which the maximum absolute and the maximum relative error are occurred at the pair of ε/D and R values, are observed. A limiting case of the most of these approximations provided friction factor estimates that are characterized by a mean absolute error of 5 × 10^?4, a maximum absolute error of 4 × 10^?3 whereas, a mean relative error of 1.3% and a maximum relative error of 5.8%, over the entire range of ε/D and R values, respectively. For practical purposes, the complete results for the maximum and the mean relative errors versus the 20 sets of ε/D value, are also indicated in two comparative figures. The examination results for error properties of these approximations gives one an opportunity to practically evaluate the most accurate formula among of all the previous explicit models; and showing in this way its great flexibility for estimating turbulent flow friction factor. Comparative analysis for the mean relative error profile revealed, the classification for the best-fitted six equations examined was in a good agreement with those of the best model selection criterion claimed in the recent literature, for all performed simulations.     

Bin packing problems with rejection penalties and their dual problems

In this paper we consider the following problems: we are given a set of n items {u₁, … , u_n} and a number of unit-capacity bins. Each item u_i has a size w_i ∈ (0, 1] and a penalty p_i ⩾ 0. An item can be either rejected, in which case we pay its penalty, or put into one bin under the constraint that the total size of the items in the bin is no greater than 1. No item can be spread into more than one bin. The objective is to minimize the total number of used bins plus the total penalty paid for the rejected items. We call the problem bin packing with rejection penalties, and denote it as BPR. For the on-line BPR problem, we present an algorithm with an absolute competitive ratio of 2.618 while the lower bound is 2.343, and an algorithm with an asymptotic competitive ratio arbitrarily close to 1.75 while the lower bound is 1.540. For the off-line BPR problem, we present an algorithm with an absolute worst-case ratio of 2 while the lower bound is 1.5, and an algorithm with an asymptotic worst-case ratio of 1.5. We also study a closely related bin covering version of the problem. In this case p_i means some amount of profit. If an item is rejected, we get its profit, or it can be put into a bin in such a way that the total size of the items in the bin is no smaller than 1. The objective is to maximize the number of covered bins plus the total profit of all rejected items. We call this problem bin covering with rejection (BCR). For the on-line BCR problem, we show that no algorithm can have absolute competitive ratio greater than 0, and present an algorithm with asymptotic competitive ratio 1/2, which is the best possible. For the off-line BCR problem, we also present an algorithm with an absolute worst-case ratio of 1/2 which matches the lower bound.     

A Fast Euclidean Algorithm for Gaussian Integers

A new version of the Euclidean algorithm is developed for computing the greatest common divisor of two Gaussian integers. It uses approximation to obtain a sequence of remainders of decreasing absolute values. The algorithm is compared with the new (1  +  i)-ary algorithm of Weilert and found to be somewhat faster if properly implemented.     

Solutions to the functional equation I(x, y) = I(x, I(x, y)) for three types of fuzzy implications derived from uninorms

This paper investigates an iterative Boolean-like law with fuzzy implications derived from uninorms. More precisely, we characterize the solutions to the functional equation I(x, y) = I(x, I(x, y)) that involve RU-, (U, N)- and QLU-implications generated by the most usual classes of uninorms.     

Curves of Genus 2 with (N,N) Decomposable Jacobians

Let C be a curve of genus 2 and ψ₁: C  −  → E ₁  a map of degree n, from C to an elliptic curveE₁ , both curves defined over C. This map induces a degree n map φ₁:P¹  −  → P ¹  which we call a Frey–Kani covering. We determine all possible ramifications for φ₁. If ψ₁:C  −  → E ₁  is maximal then there exists a maximal map ψ₂: C  −  → E ₂  , of degree n, to some elliptic curveE₂ such that there is an isogeny of degree n²from the JacobianJ_C to E₁ × E₂. We say thatJ_C is (n, n)-decomposable. If the degree n is odd the pair (ψ₂, E₂) is canonically determined. For n =  3, 5, and 7, we give arithmetic examples of curves whose Jacobians are (n, n)-decomposable.     

An Algorithm for the Quillen–Suslin Theorem for Quotients of Polynomial Rings by Monomial Ideals

This paper presents an algorithm for the Quillen–Suslin Theorem for quotients of polynomial rings by monomial ideals, that is, quotients of the form A = k [ x₀, . . . ,x_n ] / I, with I a monomial ideal and k a field. Vorst proved that finitely generated projective modules over such algebras are free. Given a finitely generated module P, described by generators and relations, the algorithm tests whether P is projective, in which case it computes a free basis forP .     

The STO problem is NP-complete

We prove that the problem STO of deciding whether or not a finite setEof term equations is subject to occur-check is in NP.Eis subject to occur-check if the execution of the Martelli–Montanari unification algorithm gives for inputEa setE^′  ∪ {x = t}, wheret ≠ xandxappears int. Aptet al. (1994) proved that STO is NP-hard leaving the problem of NP-completeness open.     

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.