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.     

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.     

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.     

Search space reduction in QoS routing

To provide real-time service or engineer constrained-based paths, networks require the underlying routing algorithm to be able to find low-cost paths that satisfy given quality-of-service constraints. However, the problem of constrained shortest (least-cost) path routing is known to be NP-hard, and some heuristics have been proposed to find a near-optimal solution. However, these heuristics either impose relationships among the link metrics to reduce the complexity of the problem which may limit the general applicability of the heuristic, or are too costly in terms of execution time to be applicable to large networks. In this paper, we focus on solving the delay-constrained minimum-cost path problem, and present a fast algorithm to find a near-optimal solution. This algorithm, called delay-cost-constrained routing (DCCR), is a variant of the k-shortest-path algorithm. DCCR uses a new adaptive path weight function together with an additional constraint imposed on the path cost, to restrict the search space. Thus, DCCR can return a near-optimal solution in a very short time. Furthermore, we use a variant of the Lagrangian relaxation method proposed by Handler and Zang [Networks 10 (1980) 293] to further reduce the search space by using a tighter bound on path cost. This makes our algorithm more accurate and even faster. We call this improved algorithm search space reduction + DCCR (SSR + DCCR). Through extensive simulations, we confirm that SSR + DCCR performs very well compared to the optimal but very expensive solution.     

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.     

A new class of massively parallel direction splitting for the incompressible Navier–Stokes equations

We introduce in this paper a new direction splitting algorithm for solving the incompressible Navier–Stokes equations. The main originality of the method consists of using the operator (I ? ?_xx)(I ? ?_yy)(I ? ?_zz) for approximating the pressure correction instead of the Poisson operator as done in all the contemporary projection methods. The complexity of the proposed algorithm is significantly lower than that of projection methods, and it is shown the have the same stability properties as the Poisson-based pressure-correction techniques, either in standard or rotational form. The first-order (in time) version of the method is proved to have the same convergence properties as the classical first-order projection techniques. Numerical tests reveal that the second-order version of the method has the same convergence rate as its second-order projection counterpart as well. The method is suitable for parallel implementation and preliminary tests show excellent parallel performance on a distributed memory cluster of up to 1024 processors. The method has been validated on the three-dimensional lid-driven cavity flow using grids composed of up to 2 × 10⁹ points.     

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.     

Constructing a novel mortality prediction model with Bayes theorem and genetic algorithm

Intensive care is one of the most important components of the modern medical system. Healthcare professionals need to utilize intensive care resources effectively. Mortality prediction models help physicians decide which patients require intensive care the most and which do not. The Simplified Acute Physiology System 2nd version (SAPS II) is one of the most popular mortality scoring systems currently available. This study retrospectively collected data on 496 patients admitted to intensive care units from year 2000 to 2001. The average patient age was 59.96 ± 1.83 years old and 23.8% of patients died before discharge. We used these data as training data and constructed an exponential Bayesian mortality prediction model by combining BSM (Bayesian statistical model) and GA (genetic algorithm). The optimal weights and the parameters were determined with GA. Furthermore, we prospectively collected data on 142 patients for testing the new model. The average patient age for this group was 57.80 ± 3.33 years old and 21.8% patients died before discharge. The mortality prediction power of the new model was better than SAPS II (p < 0.001). The new model combining BSM and GA can manage both binary data and continuous data. The mortality rate is predicted to be high if the patient’s Glasgow coma score is less than 5.     

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.     

Deadline-based scheduling in support of real-time data delivery

The use of deadline-based scheduling in support of real-time delivery of application data units (ADUs) in a packet-switched network is investigated. Of interest is priority scheduling where a packet with a smaller ratio of T/H (time until delivery deadline over number of hops remaining) is given a higher priority. We refer to this scheduling algorithm as the T/H algorithm. T/H has time complexity of O(log N) for a backlog of N packets and was shown to achieve good performance in terms of the percentage of ADUs that are delivered on-time. We develop a new and efficient algorithm, called T/H − p, that has O(1) time complexity. The performance difference of T/H, T/H − p and FCFS are evaluated by simulation. Implementations of T/H and T/H − p in high-speed routers are also discussed. We show through simulation that T/H − p is superior to FCFS but not as good as T/H. In view of the constant time complexity, T/H − p is a good candidate for high-speed routers when both performance and implementation cost are taken into consideration.     

A hybrid classifier combining SMOTE with PSO to estimate 5-year survivability of breast cancer patients

In this study, we propose a set of new algorithms to enhance the effectiveness of classification for 5-year survivability of breast cancer patients from a massive data set with imbalanced property. The proposed classifier algorithms are a combination of synthetic minority oversampling technique (SMOTE) and particle swarm optimization (PSO), while integrating some well known classifiers, such as logistic regression, C5 decision tree (C5) model, and 1-nearest neighbor search. To justify the effectiveness for this new set of classifiers, the g-mean and accuracy indices are used as performance indexes; moreover, the proposed classifiers are compared with previous literatures. Experimental results show that the hybrid algorithm of SMOTE + PSO + C5 is the best one for 5-year survivability of breast cancer patient classification among all algorithm combinations. We conclude that, implementing SMOTE in appropriate searching algorithms such as PSO and classifiers such as C5 can significantly improve the effectiveness of classification for massive imbalanced data sets.     

Symmetric and symplectic exponentially fitted Runge–Kutta–Nyström methods for Hamiltonian problems

The construction of symmetric and symplectic exponentially fitted modified Runge–Kutta–Nyström (SSEFRKN) methods is considered. Based on the symmetry, symplecticity, and exponentially fitted conditions, new explicit modified RKN integrators with FSAL property are obtained. The new integrators integrate exactly differential systems whose solutions can be expressed as linear combinations of functions from the set { exp(± iωt)}, ω > 0, i² = −1, or equivalently from the set { cos(ωt), sin(ωt)}. The phase properties of the new integrators are examined and their periodicity regions are obtained. Numerical experiments are accompanied to show the high efficiency and competence of the new SSEFRKN methods compared with some highly efficient nonsymmetric symplecti EFRKN methods in the literature.     

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.     

A ranking procedure based on a natural monotonicity constraint

We formulate a new ranking procedure in the traditional context where each voter has expressed a linear order relation or ranking over the candidates. The final ranking of the candidates is taken to be the one which best adheres to a natural monotonicity constraint. For a ranking a ≻ b ≻ c, monotonicity implies that the strength with which a ≻ c is supported should not be less than the strength with which either one of a ≻ b or b ≻ c is supported. We investigate some properties of this ranking procedure and encounter some surprising preliminary results.     

A combinatorial particle swarm optimisation for solving permutation flowshop problems

The m-machine permutation flowshop problem PFSP with the objectives of minimizing the makespan and the total flowtime is a common scheduling problem, which is known to be NP-complete in the strong sense, when m ? 3. This work proposes a new algorithm for solving the permutation FSP, namely combinatorial Particle Swarm Optimization. Furthermore, we incorporate in this heuristic an improvement procedure based on the simulated annealing approach. The proposed algorithm was applied to well-known benchmark problems and compared with several competing metaheuristics.     

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.     

Computational assessment of several hydrogen-free high energy compounds

Tetrazino-tetrazine-tetraoxide (TTTO) is an attractive high energy compound, but unfortunately, it is not yet experimentally synthesized so far. Isomerization of TTTO leads to its five isomers, bond-separation energies were empolyed to compare the global stability of six compounds, it is found that isomer 1 has the highest bond-separation energy (1204.6 kJ/mol), compared with TTTO (1151.2 kJ/mol); thermodynamic properties of six compounds were theoretically calculated, including standard formation enthalpies (solid and gaseous), standard fusion enthalpies, standard vaporation enthalpies, standard sublimation enthalpies, lattice energies and normal melting points, normal boiling points; their detonation performances were also computed, including detonation heat (Q, cal/g), detonation velocity (D, km/s), detonation pressure (P, GPa) and impact sensitivity (h₅₀, cm), compared with TTTO (Q = 1311.01 J/g, D = 9.228 km/s, P = 40.556 GPa, h₅₀ = 12.7 cm), isomer 5 exhibites better detonation performances (Q = 1523.74 J/g, D = 9.389 km/s, P = 41.329 GPa, h₅₀ =  28.4 cm).     

Implicitization of a General Union of Parametric Varieties

We reconduct the computation of the equations defining a union V of parametric varieties, up to a given degree d, to the computation of the equations, of degree  ≤ d, vanishing on a finite set of points of V. If V is general this gives a new algorithm for implicitizing V. We have compared the implementation of this algorithm with the Hilbert-driven elimination algorithm included in the software packages CoCoA 3.7 and Singular 1.2, obtaining significant time savings. Moreover, the implementation of the algorithm leads to two intriguing conjectures on the natural number of generators of the union of general parametric curves or surfaces.     

Weyl Closure of a Linear Differential Operator

We study the Weyl closure Cl(L)  = K(x)〈∂〉L ∩ D for an operator L of the first Weyl algebra D = K〈x, ∂〉. We give an algorithm to compute Cl(L) and we describe its initial ideal under the order filtration. Our main application is an algorithm for constructing a Jordan–Hölder series for a holonomic D -module and a formula for its length. Using the closure, we also reproduce a result ofStrömbeck (1978), who described the initial ideals of left ideals of D under the order filtration, and a result ofCannings and Holland (1994), who described the isomorphism classes of right ideals of D.