The improved Farmer–Loizou method for finding polynomial zeros

An improvement of the Farmer–Loizou method for the simultaneous determination of simple roots of algebraic polynomials is proposed. Using suitable corrections of Newton's type, the convergence of the basic method is increased from 4 to 5 without any additional calculations. In this manner, a higher computational efficiency of the improved method is achieved. We prove a local convergence of the presented method under initial conditions which depend on a geometry of zeros and their initial approximations. Numerical examples are given to demonstrate the convergence behaviour of the proposed method and related methods.     

A Parallel Algorithm for Finding Roots of a Complex Polynomial

A distribution theory of the roots of a polynomial and a parallel algorithm for finding roots of a complex polynomial based on that theory are developed in this paper.With high parallelism,the algorithm is an improvement over the Wilf algorithm^[3].     

Approximation Algorithms for Bounded Degree Phylogenetic Roots

The Degree- Δ Closest Phylogenetic k th Root Problem (ΔCPR _k ) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E ⊕{{u,v} : u,v are leaves of T and d _T (u,v)≤k}|, is minimized, where d _T (u,v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Δ,k such that either both Δ≥3 and k≥3, or Δ>3 and k=2. This paper presents a polynomial-time 8-approximation algorithm for Δ CPR ₂ for any fixed Δ>3, a quadratic-time 12-approximation algorithm for 3CPR ₃, and a polynomial-time approximation scheme for the maximization version of Δ CPR _k for any fixed Δ and k.     

Comments on Samal and Henderson: “Parallel consistent labeling algorithms”

Samal and Henderson claim that any parallel algorithm for enforcing arc consistency in the worst case must have (na) sequential steps, wheren is the number of nodes, anda is the number of labels per node. We argue that Samal and Henderson's argument makes assumptions about how processors are used and give a counterexample that enforces arc consistency in a constant number of steps usingO(n[su2a²2^na) processors. It is possible that the lower bound holds for a polynomial number of processors; if such a lower bound were to be proven it would answer an important open question in theoretical computer science concerning the relation between the complexity classesP andNC. The strongest existing lower bound for the arc consistency problem states that it cannot be solved in polynomial log time unlessP=NC.     

Parallel spatiotemporal autocorrelation and visualization system for large-scale remotely sensed images

Current studies on large-scale remotely sensed images are of great national importance for monitoring and evaluating global climate and ecological changes. In particular, real time distributed high-performance visualization and computation have become indispensable research components in facilitating the extraction of remotely sensed image textures to enable mining spatiotemporal patterns and dynamics of landscapes from massive geo-digital information collected from satellites. Remotely sensed images are usually highly correlated with rich landscape features. By exploiting the structures of these images and extracting their textures, fundamental insights of the landscape can be derived. Furthermore, the interdisciplinary collaboration on the remotely sensed image analysis demands multifarious expertise in a wide spectrum of fields including geography, computer science, and engineering.     

Distributed scheduling algorithms for channel access in TDMA wireless mesh networks

In this paper, we have considered the distributed scheduling problem for channel access in TDMA wireless mesh networks. The problem is to assign time-slot(s) for nodes to access the channels, and it is guaranteed that nodes can communicate with all their one-hop neighbors in the assigned time-slot(s). And, the objective is to minimize the cycle length, i.e., the total number of different time-slots in one scheduling cycle. In single-channel ad hoc networks, the best known result for this problem is proved to be K ² in arbitrary graphs (Chlamtac and Pinter in IEEE Trans. Comput. C-36(6):729–737, 1987) and 25K in unit disk graphs () with K as the maximum node degree. There are multiple channels in wireless mesh networks, and different nodes can use different control channels to reduce congestion on the control channels. In this paper, we have considered two scheduling models for wireless mesh networks. The first model is that each node has two radios, and the scheduling is simultaneously done on the two radios. We have proved that the upper bound of the cycle length in arbitrary graphs can be 2K. The second model is that the time-slots are scheduled for the nodes regardless of the number of radios on them. In this case, we have proved that the upper bound can be (4K−2). We also have proposed greedy algorithms with different criterion. The basic idea of these algorithms is to organize the conflicting nodes by special criterion, such as node identification, node degree, the number of conflicting neighbors, etc. And, a node cannot be assigned to a time-slot(s) until all neighbor nodes, which have higher criterion and might conflict with the current node, are assigned time-slot(s) already. All these algorithms are fully distributed and easy to realize. Simulations are also done to verify the performance of these algorithms.     

Effective on-line algorithms for reliable due date quotation and large-scale scheduling

We consider the sequencing of a series of jobs that arrive at a single processor over time. At each job’s arrival time, a due date must be quoted for the job, and the job must complete processing before its quoted due date. The objective is to minimize the sum (or average) of quoted due dates, or equivalently, the average quoted lead time. In this paper, we propose on-line heuristics for this problem and characterize the conditions under which these heuristics are asymptotically optimal. Computational testing further demonstrates the relative effectiveness of these heuristics under various conditions. Both authors made equal contributions to this paper and are listed in alphabetical order.     

Distributed scheduling algorithms for channel access in TDMA wireless mesh networks

In this paper, we have considered the distributed scheduling problem for channel access in TDMA wireless mesh networks. The problem is to assign time-slot(s) for nodes to access the channels, and it is guaranteed that nodes can communicate with all their one-hop neighbors in the assigned time-slot(s). And the objective is to minimize the cycle length, i.e., the total number of different time-slots in one scheduling cycle. In single-channel ad hoc networks, the best known result for this problem is proved to be K ² in arbitrary graphs (IEEE Trans Comput C-36(6):729–737, 1987) and 25K in unit disk graphs (IEEE/ACM Trans Netw pp 166–177, 1993) with K as the maximum node degree. There are multiple channels in wireless mesh networks, and different nodes can use different control channels to reduce congestion on the control channels. In this paper, we have considered two scheduling models for wireless mesh networks. The first model is that each node has two radios, and the scheduling is simultaneously done on the two radios. We have proved that the upper bound of the cycle length in arbitrary graphs can be 2K. The second model is that the time-slots are scheduled for the nodes regardless of the number of radios on them. In this case, we have proved that the upper bound can be (4K?2). We also have proposed greedy algorithms with different criterion. The basic idea of these algorithms is to organize the conflicting nodes by special criterion, such as node identification, node degree, the number of conflicting neighbors, etc. And a node cannot be assigned to a time-slot(s) until all neighbor nodes, which have higher criterion and might conflict with the current node, are assigned time-slot(s) already. All these algorithms are fully distributed and easy to realize. Simulations are also done to verify the performance of these algorithms.     

A Prolate-Element Method for Nonlinear PDEs on the Sphere

A p-type spectral-element method using prolate spheroidal wave functions (PSWFs) as basis functions, termed as the prolate-element method, is developed for solving partial differential equations (PDEs) on the sphere. The gridding on the sphere is based on a projection of the prolate-Gauss-Lobatto points by using the cube-sphere transform, which is free of singularity and leads to quasi-uniform grids. Various numerical results demonstrate that the proposed prolate-element method enjoys some remarkable advantages over the polynomial-based element method: (i) it can significantly relax the time step size constraint of an explicit time-marching scheme, and (ii) it can increase the accuracy and enhance the resolution.     

Recursive formulations for multibody systems with frictional joints based on the interaction between bodies

In practice, the clearances of joints in a great number of mechanical systems are well under control. In these cases, some of the existing methods become unpractical because of the little differences in the order of magnitude between relative movements and computational errors. Assuming that the effects of impacts are negligible, we proved that both locations and forces of contacts in joints can be fully determined by parts of joint reaction forces. Based on this fact, a method particularly suited for multibody systems possessing frictional joints with tiny clearances is presented. In order to improve the efficiency of computation, recursive formulations are proposed based on the interactions between bodies. The proposed recursive formulations can improve the computation of joint reaction forces. With the methodology presented in this paper, not only the motion of bodies in a multibody system but also the details about the contacts in joints, such as forces of contacts and locations of contact points, can be obtained. Even with the assumption of impact free, the instants of possible impacts can be detected without relying upon any ambiguous parameters, as indicated by numerical examples in this paper.     

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

Compiler support for general-purpose computation on GPUs

In recent years, the GPU (graphics processing unit) has evolved into an extremely powerful and flexible processor, with it now representing an attractive platform for general-purpose computation. Moreover, changes to the design and programmability of GPUs provide the opportunity to perform general-purpose computation on a GPU (GPGPU). Even though many programming languages, software tools, and libraries have been proposed to facilitate GPGPU programming, the unusual and specific programming model of the GPU remains a significant barrier to writing GPGPU programs. In this paper, we introduce a novel compiler-based approach for GPGPU programming. Compiler directives are used to label code fragments that are to be executed on the GPU. Our GPGPU compiler, Guru, converts the labeled code fragments into ISO-compliant C code that contains appropriate OpenGL and Cg APIs. A native C compiler can then be used to compile it into the executable code for GPU. Our compiler is implemented based on the Open64 compiler infrastructure. Preliminary experimental results from selected benchmarks show that our compiler produces significant performance improvements for programs that exhibit a high degree of data parallelism.     

On the application of the minimum polynomial extrapolation method to incompressible flows with heat transfer

In this paper, the Minimum Polynomial Extrapolation method (MPE) is used to accelerate the convergence of the Characteristic–Based–Split (CBS) scheme for the numerical solution of steady state incompressible flows with heat transfer. The CBS scheme is a fractional step method for the solution of the Navier–Stokes equations while the MPE method is a vector extrapolation method which transforms the original sequence into another sequence converging to the same limit faster then the original one without the explicit knowledge of the sequence generator. The developed algorithm is tested on a two-dimensional benchmark problem (buoyancy–driven convection problem) where the Navier–Stokes equations are coupled with the temperature equation. The obtained results show the feature of the extrapolation procedure to the CBS scheme and the reduction of the computational time of the simulation.     

A new model for the integrated vehicle-crew-rostering problem and a computational study on rosters

Operational planning within public transit companies has been extensively tackled but still remains a challenging area for operations research models and techniques. This phase of the planning process comprises vehicle-scheduling, crew-scheduling and rostering problems. In this paper, a new integer mathematical formulation to describe the integrated vehicle-crew-rostering problem is presented. The method proposed to obtain feasible solutions for this binary non-linear multi-objective optimization problem is a sequential algorithm considered within a preemptive goal programming framework that gives a higher priority to the integrated vehicle-crew-scheduling goal and a lower priority to the driver rostering goals. A heuristic approach is developed where the decision maker can choose from different vehicle-crew schedules and rosters, while respecting as much as possible management’s interests and drivers’ preferences. An application to real data of a Portuguese bus company shows the influence of vehicle-crew-scheduling optimization on rostering solutions.